This is the August edition of Favorite Theorems.
Perhaps you could easily find a satisfying assignment of a Boolean formula when only one solution exists, somehow using the uniqueness to cleverly guide your search. Valiant and Vazirani show that any such procedure would give a randomized algorithm for general satisfiability and put the class NP in RP.
Valiant and Vazirani show there is some efficient randomized algorithm f mapping Boolean formula to Boolean formula such that for all formula φ,
- f(φ) will always have the same set of variables of φ and every satisfying assignment of f(φ) is a satisfying assignment of φ. In particular if φ is not satisfiable then f(φ) is never satisfiable.
- If φ is satisfiable then Pr(f(φ) has exactly one satisfying assignment) ≥ 1/(4n), where n is the number of variables of φ.
Valiant and Vazirani's proof takes random half-spaces of the solution set and argues that with some reasonable probability repeating this process will yield a single solution. The techniques are quite general and one can get similar results for nearly every known NP problem.
Mulmuley, Vazirani and Vazirani prove an "isolating lemma" which one can use to give an alternate proof of a similar theorem by putting random weights on edges and with some reasonable probability there is a unique maximum weight clique. Mulmuley et. al. use the isolating lemma to give a simple randomized parallel algorithm for maximum matching.
Besides the immediate hardness of finding unique solutions, Valiant-Vazirani has had impact in complexity in many ways. Just a couple:
- One can use Valiant-Vazirani to find a satisfying assignment of a formula using non-adaptive queries to SAT.
- Valiant-Vazirani gives the base case of Toda's theorem.
- Similar ideas show how to create a low-degree polynomial that correctly computes the OR function at most inputs (which one can extend to AC0 by recursion).
ECCC TR06-062
ReplyDeleteIsolation Lemma of [MVV87] was used to prove NL/poly = UL/poly by Reinhardt and Allender. To show that NL/poly = UL/poly it is sufficient to show that NL/poly \subseteq UL/poly, other side is implied by definition, for which one can present a UL/poly algorithm for problem STCONN. However, to do this in UL, one have to reduce STCONN to a problem of finding a unique path in the input graph G from s to t. This was done by a reduction used by Wigderson to show NL/poly \subseteq \Oplus L/poly. Reduction works in logspace by assigning random weights (between [1,4.|V|^2.|E|]) to the edges of the graph, while ensuring that there will be a unique minimum weight s-t-path on weighted graph with high probability iff there is one s-t-path in original graph (i.e. a RL reduction), and then turning the weighted graph back to a unweighted graph while preserving the reduction. In fact this weight assignment can ensure that the shortest distance between every pair of nodes is achieved by a unique path with high probability (call it min unique graph). A weight function is then ``good'' if it converts the graph to a min unique graph. A simple counting argument shows that in a collection of polynomially many random weight functions one is ``good'' for every possible input graphs.
ReplyDeleteAlso, see some more application of isolation lemma in complexity of Matching (``Isolation, Matching, and Counting: Uniform and Nonuniform Upper Bounds'',Eric Allender and Klaus Reinhardt and S. Zhou)
See Hemaspaandra and Ogihara's book for a chapter on Isolation Lemma.
Stasys Jukna's book ``Extremal Combinatorics'' has a section on Isolation.
What's up with ECCC TR06-062?
ReplyDeleteThere seem to be much of a discussion around this report. Is the proof there valid?
No! Proof of ECCC TR06-062 still has some problem.
ReplyDeleteI am not sure if an incomplete result deserves much discussion - but the reason for which it was discussed was following:
Is ECCC kind of model "good"? Where good-ness was observed from various perspective, namely and most importantly can author timestamp work by ECCC submission and claim that the "proof belongs to him".
I rather see the purpose of submitting a paper in ECCC as a way to receive peer-review comments. I am not sure if this is an inverted way of using ECCC (people seem to have opposite view point). For me, neither do I see it embarrassing to get my mistakes reviewed by others nor do I intend to submit so that I can claim that the "proof belongs to me"(hard to prove this claim though :), but following explanation might serve).
I do not belong to academia, and I do not find much opportunity to get my works discussed with others or get them reviewed. I did not indented to live with that, and rather decided to post in ECCC – as even one constructive comment will be worth for me, which will allow me to correct my work quickly. It is rather in this desperation the ``problematic paper’’ exists as TR06-062. While I must say I am grateful to, Chris Calabro and Yann Barsamian, who commented on the earlier version, and I am working on them.
One final comment: First comment in this post:
Anonymous said...
ECCC TR06-062
9:47 PM, September 02, 2006
Is not posted by me, :) of course I would not want this to be discussed much - before I complete my duty (i.e. correct my work).