en>Mark viking: Added wl

2014-01-12T00:43:00Z

Added wl

← Older revision		Revision as of 02:43, 12 January 2014
Line 1:		Line 1:
	~~I would like to introduce myself to you, I am Andrew and my wife doesn~~'~~t like it at all~~. ~~The preferred~~ [~~http://www~~.~~zavodpm~~.~~ru/blogs/glennmusserrvji~~/~~14565~~-~~great~~-~~hobby~~-~~advice~~-~~assist~~-~~allow-you-get-going certified psychics~~] ~~pastime~~ for ~~him~~ and ~~his kids is to perform lacross and he would by no means give~~ it up. ~~North Carolina~~ is the ~~location he enjoys~~ most ~~but now he~~ [~~http:~~//~~www~~.~~khuplaza.com~~/~~dent~~/~~14869889 love psychic]~~ is ~~contemplating other options~~. ~~Office supervising is what she does for~~ a ~~residing~~.<br><br>~~My blog post :: live psychic reading; [http:~~//~~modenpeople~~.co.kr/~~modn~~/~~qna~~/~~292291 http:~~/~~/modenpeople~~.co.kr/~~modn~~/~~qna/292291~~],		The '''Valiant–Vazirani theorem''' is a theorem in [[computational complexity theory]]. It was proven by [[Leslie Valiant]] and [[Vijay Vazirani]] in their paper titled ''NP is as easy as detecting unique solutions'' published in 1986.<ref>{{cite doi\|10.1016/0304-3975(86)90135-0}}</ref>
			The theorem states that if there is a [[P (complexity)\|polynomial time algorithm]] for [[Boolean satisfiability problem#Extensions of SAT\|Unambiguous-SAT]], then [[NP (complexity)\|NP]]=[[RP (complexity)\|RP]].
			The proof is based on the Mulmuley–Vazirani [[isolation lemma]], which was subsequently used for a number of important applications in [[theoretical computer science]].

			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.

			==Proof outline==
			[[Boolean satisfiability problem#Extensions of SAT\|Unambiguous-SAT]] is the [[promise problem]] of deciding whether a given Boolean formula that has at most one satisfying assignment is unsatisfiable or has exactly one satisfying assignment. In the first case, an algorithm for Unambiguous-SAT should reject, and in the second it should accept the formula.
			If the formula has more than one satisfying assignment, then there is no condition on the behavior of the algorithm.
			The promise problem Unambiguous-SAT can be decided by a [[nondeterministic Turing machine]] that has at most one accepting computation path. In this sense, this promise problem belongs to the complexity class [[UP (complexity)\|UP]] (which is usually only defined for languages).

			The proof of the Valiant–Vazirani theorem consists of a probabilistic reduction from SAT to SAT such that, with probability at least <math>\Omega(1/n)</math>, the output formula has at most one satisfying assignment, and thus satisfies the promise of the Unambiguous-SAT problem.
			More precisely, the reduction is a randomized polynomial-time algorithm that maps a Boolean formula <math>F(x_1,\dots,x_n)</math> with <math>n</math> variables <math>x_1,\dots,x_n</math> to a Boolean formula <math>F'(x_1,\dots,x_n)</math> such that
			* every satisfying assignment of <math>F'</math> also satisfies <math>F</math>, and
			* if <math>F</math> is satisfiable, then, with probability at least <math>\Omega(1/n)</math>, <math>F'</math> has a unique satisfying assignment <math>(a_1,\dots,a_n)</math>.

			By running the reduction a polynomial number <math>t</math> of times, each time with fresh independent random bits, we get formulas <math>F'_1,\dots,F'_t</math>.
			Choosing <math>t=O(n)</math>, we get that the probability that at least one formula <math>F'_i</math> is uniquely satisfiable is at least <math>1/2</math> if <math>F</math> is satisfiable.
			This gives a Turing reduction from SAT to Unambiguous-SAT since an assumed algorithm for Unambiguous-SAT can be invoked on the <math>F'_i</math>. Then the [[random self-reducibility]] of SAT can be used to compute a satisfying assignment, should it exist.
			Overall, this proves that NP=RP if Unambiguous-SAT can be solved in RP.

			The idea of the reduction is to intersect the solution space of the formula <math>F</math> with <math>k</math> random affine hyperplanes over <math>\text{GF}(2)^n</math>, where <math>k\in\{1,\dots,n\}</math> is chosen uniformly at random.
			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 <math>\Omega(1/n^8)</math>.

			==References==
			{{reflist}}

			{{DEFAULTSORT:Valiant-Vazirani theorem}}
			[[Category:Structural complexity theory]]
			[[Category:Theorems in computational complexity theory]]

en>Brad7777: removed Category:Complex manifolds; added Category:Theorems in complex geometry using HotCat

2012-02-04T16:51:17Z

removed Category:Complex manifolds; added Category:Theorems in complex geometry using HotCat

New page

I would like to introduce myself to you, I am Andrew and my wife doesn't like it at all. The preferred [http://www.zavodpm.ru/blogs/glennmusserrvji/14565-great-hobby-advice-assist-allow-you-get-going certified psychics] pastime for him and his kids is to perform lacross and he would by no means give it up. North Carolina is the location he enjoys most but now he [http://www.khuplaza.com/dent/14869889 love psychic] is contemplating other options. Office supervising is what she does for a residing.<br><br>My blog post :: live psychic reading; [http://modenpeople.co.kr/modn/qna/292291 http://modenpeople.co.kr/modn/qna/292291],

Torelli theorem - Revision history

en>Mark viking: Added wl

en>Brad7777: removed Category:Complex manifolds; added Category:Theorems in complex geometry using HotCat