Кіріспе
Егер біркелкі SAT үшін көпмүшелік уақыт алгоритмі болса, онда NP = RP. Валиант-Вазирани теоремасы – есептеу күрделілігі теориясындағы теорема, егер біркелкі SAT үшін көпмүшелік уақыт алгоритмі болса, онда NP = RP. Лесли Валиант пен Виджай Вазирани бұл теореманы 1986 жылы жарияланған «NP is as easy as detecting unique solutions» атты мақаласында дәлелдеген. Валиант-Вазирани теоремасы Бульдік қанағаттандыру мәселесінің NP-толық екенін көрсетеді, тіпті егер кіріс мысалдарына ең көп дегенде бір қанағаттандыратын тапсырма берілсе де, ол есептеу жағынан қиын мәселе болып қалады.
The Valiant–Vazirani theorem is a theorem in computational complexity theory stating that if there is a polynomial time algorithm for Unambiguous SAT, then NP = RP. It was proven by Leslie Valiant and Vijay Vazirani in their paper titled NP is as easy as detecting unique solutions published in 1986. The Valiant–Vazirani theorem implies that the Boolean satisfiability problem, which is NP complete, remains a computationally hard problem even if the input instances are promised to have at most one satisfying assignment.
Дәлелдің конспектісі
Біржақты SAT – бұл ең көп дегенде бір қанағаттандыратын тапсырмасы бар Буль формуласының қанағаттандырылмайтын немесе дәл бір қанағаттандыратын тапсырмасы бар екенін шешудің уәдесіз проблемасы. Бірінші жағдайда, Біржақты SAT алгоритмі оны қабылдамауы керек, ал екінші жағдайда – қабылдауы керек. Егер формуланың бірнеше қанағаттандыратын тапсырмасы болса, алгоритмнің қызметіне ешқандай талап қойылмайды. Біржақты SAT уәдесіз проблемасын ең көп дегенде бір қабылдау есептеу жолы бар детерминистік емес Тьюринг машинасымен шешуге болады, сондықтан ол UP күрделілік класының уәделі нұсқасына жатады (UP класы тілдер үшін ғана анықталған). Валиант-Вазирани теоремасының дәлелі н айнымалысы бар F формуласы берілгенде G0, …, Gn формулаларының тізбесін шығаратын ықтималдық азайтудан тұрады: кез келген Gi формуласының кез келген қанағаттандыратын тапсырмасы F формуласын да қанағаттандырады. Егер F қанағаттандырылмаса, онда барлық Gi (i ≤ n) қанағаттандырылмайды. Егер F қанағаттандырылса, онда кем дегенде 1/4 ықтималдығымен кейбір Gi-де бірегей қанағаттандыратын тапсырма болады. Азайту идеясы – F формуласының шешім кеңістігін n кездейсоқ сызықтық гипержазымен біртіндеп қиып алу болып табылады. Салдары ретінде (NP = RP аргументі үшін қажет емес, бірақ жеке қызығушылық тудырады), егер Gi формулаларының біреуін кездейсоқ таңдасақ, онда SAT-тен Біржақты SAT-қа бір жақты қатемен ықтималдық азайтуға қол жеткіземіз, ол кем дегенде Ω(1/n) ықтималдығымен сәтті аяқталады. Яғни, егер F қанағаттандырылмаса, шығыс формуласы әрқашан қанағаттандырылмайды, ал егер F қанағаттандырылса, онда шығыс формуласы Ω(1/n) ықтималдығымен бірегей қанағаттандыратын тапсырмаға ие болады. Енді, егер Біржақты SAT полиномдық уақыт алгоритмі A-мен шешілетін болса, онда SAT үшін RP алгоритмін алуға болады, A-ны Gi формуласына әр i ≤ n үшін орындай отырып. Егер F қанағаттандырылмаса, онда A барлық Gi формулаларын қанағаттандырылмаған деп қабылдамайды, ал егер F қанағаттандырылса, онда A кем дегенде 1/4 ықтималдығымен кейбір Gi формуласын қабылдайды. (Қабылдау ықтималдығын арттыру үшін азайтуды бірнеше рет қайталауға болады.) Жалпы алғанда, бұл аргумент NP күрделілік класының RPpromiseUP класына кіретінін дәлелдейді. Балама дәлел Мулмули, Вазирани және Вазиранидің оқшаулау леммасына негізделген. Олар одан да жалпы жағдайды қарастырады, ал осы жағдайға қолданғанда оқшаулау ықтималдығы тек . құрайды.
Every satisfying assignment of any Gi also satisfies F. Thus, if F is unsatisfiable, then all Gi, i ≤ n, are unsatisfiable. If F is satisfiable, then with probability at least 1/4, some Gi has a unique satisfying assignment. The idea of the reduction is to successively intersect the solution space of the formula F with n random linear hyperplanes in
As a consequence (not needed for the NP = RP argument, but of independent interest), if we choose one of the Gi at random, we obtain a randomized reduction with one sided error from SAT to Unambiguous SAT that succeeds with probability at least Ω(1/n). That is, if F is unsatisfiable, the output formula is always unsatisfiable, and if F is satisfiable, then the output formula has a unique satisfying assignment with probability Ω(1/n). Now, assuming Unambiguous SAT is solvable by a polynomial time algorithm A, we obtain an RP algorithm for SAT by running A on Gi for each i ≤ n. If F is unsatisfiable, then A rejects all Gi as they are unsatisfiable, whereas if F is satisfiable, then A accepts some Gi with probability at least 1/4. (We can improve the acceptance probability by repeating the reduction several times.) More generally, this argument shows unconditionally that NP is included in RPpromiseUP. An alternative proof is based on the isolation lemma by Mulmuley, Vazirani, and Vazirani. They consider a more general setting, and applied to the setting here this gives an isolation probability of only .