Valiant–Vaziranis teorem

Valiant –Vazirani-satsen är ett teorem inom beräkningskomplexitetsteorin som säger att om det finns en polynomtidsalgoritm för Entydig-SAT , så är NP = RP . Det bevisades av Leslie Valiant och Vijay Vazirani i deras artikel med titeln NP är lika lätt som att upptäcka unika lösningar som publicerades 1986. Beviset är baserat på Mulmuley-Vazirani-Vazirani- isoleringslemmat , som sedan användes för ett antal viktiga tillämpningar i teoretisk datavetenskap .

Valiant–Vazirani-satsen antyder att det booleska tillfredsställbarhetsproblemet , som är NP-komplett , förblir ett beräkningsmässigt svårt problem även om ingångsinstanserna utlovas att ha högst en tillfredsställande tilldelning.

Bevisöversikt

Entydigt-SAT är löftesproblemet att avgöra om en given boolesk formel som har högst en tillfredsställande uppgift är otillfredsställande eller har exakt en tillfredsställande uppgift. I det första fallet bör en algoritm för Entydig-SAT avvisa, och i det andra ska den acceptera formeln. Om formeln har mer än en tillfredsställande tilldelning, finns det inget villkor för algoritmens beteende. Löftesproblemet Entydigt-SAT kan avgöras av en icke-deterministisk Turing-maskin som har högst en accepterande beräkningsväg. I denna mening tillhör detta löftesproblem komplexitetsklassen UP (som vanligtvis bara definieras för språk).

Beviset för Valiant–Vazirani-satsen består av en probabilistisk reduktion från SAT till SAT så att, med sannolikhet minst $\Omega (1/n)$ , utdataformeln har som mest en som uppfyller uppdraget, och uppfyller därmed löftet om entydigt-SAT-problemet. Mer exakt är reduktionen en randomiserad polynom-tidsalgoritm som mappar en boolesk formel $F(x_{1},\dots ,x_{n})$ med ${\ displaystyle n}$ variabler $x_{1},\dots ,x_{n}$ till en boolesk formel $F'(x_{ 1},\dots ,x_{n})$ så att

• varje tillfredsställande tilldelning av $F'$ uppfyller också $F$ , och
• om $F$ är tillfredsställbar, så har, med sannolikhet minst ${\displaystyle \Omega (1/n)} ,$ F $\displaystyle F'}$ en unik tillfredsställande tilldelning $(a_{1},\dots ,a_{n})$ .

Genom att köra reduktionen ett polynomantal $t$ gånger, varje gång med nya oberoende slumpmässiga bitar, får vi formlerna ${\displaystyle F'_{1},\dots ,$ . Genom att välja $displaystyle t=O(n)} får vi att$$1/2$ för att minst en formel $F'_{i}$ är unikt tillfredsställbar är minst om $F$ är tillfredsställande. Detta ger en Turing-reduktion från SAT till Unambiguous-SAT eftersom en antagen algoritm för Unambiguous-SAT kan anropas på $F'_{i}$ . Sedan självreducerbarheten för SAT användas för att beräkna ett tillfredsställande uppdrag, om det skulle finnas. Sammantaget bevisar detta att NP = RP om Unambiguous-SAT kan lösas i RP.

Tanken med reduktionen är att skära lösningsutrymmet för formeln $F$ med $k$ slumpmässiga affina hyperplan över ${\text{GF}}(2)^ {n}$ , där $k\in \{1,\dots ,n\}$ väljs enhetligt slumpmässigt. Ett alternativt bevis är baserat på isoleringslemmat av Mulmuley, Vazirani och Vazirani. De överväger en mer generell inställning, och tillämpat på inställningen här ger detta en isolationssannolikhet på endast $\Omega (1/n^{8})$ .