Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I am asking for help to explain some crucial points of the central lemma and it's proof of famous paper NP is as easy as detecting unique solutions by L.Valiant and V.Vazirani.

The proof can be found in the section 2. The proof of the paper.

The idea of the lemma: lemma shows that there is a randomized polynomial - time reduction from SAT to Unique-SAT. Lemma uses GF[2] inner product with polynomial few {0,1} vectors.

Problem in general: I have some difficulties in understanding the definition of the lemma and in usage of GF[2] for proving the lemma.

Specific questions:

Following is the number of citations from the paper with relevant question to the citation.

Lemma 2.1. If $f$ is any CNF formula in $x_1,...,x_n$ and $w_1,...,w_k \in \{0,1\}^n$,

Q:I think $x_1,...,x_n$ are literals, but what are $w_1,..,w_k$? Are they literals or something else? If yes, why to distinct between them and $x$ literals.

A:$w_1,..,w_k$ are the truth assignments.

then one can construct in linear time a formula $f'_k$ whose solution $v$ satisfy $f$ and the equations $v\cdot w_1=...=v\cdot w_k=0$. Furthermore, one can construt a polynomial-size CNF formula $f_k$ in variables $x_1,...,x_n,y_1,...y_m$,

Q: $x_1,...x_n$ are unknown literals, how can we construct $f_k$ with unknown literals and where $y_1,...,y_m$ came from?

for some $m$ such that there is a bijection between solutions of $f_k$ and $f'_k$, defined be equality on the $x_1,...,x_n$ values.

Proof: It is sufficient to show the lemma for $k=1$. Then, $f'_k$ is

$f \wedge (x_{i_1} \bigoplus x_{i_2} \bigoplus ... \bigoplus x_{i_j} \bigoplus 1)$

Q: this is the most vague point, how do we come to the such construction of $f'_1$ and why showing only $f'_1$ sufficient for the proof.

I hope you forgive me for my naivety. I will appreciate any hint in accordance to the above questions.

share|improve this question
You are confusing truth assignments and literals, and you are also confusing vectors and their components. I suggest that you read what is written in the paper more carefully. –  Tsuyoshi Ito Feb 14 '13 at 15:23
@TsuyoshiIto, thank you very much for the comment, I've added some answers, $w_1,...,w_k$ are truth assignments, however the entire idea of the prof is still vague. –  fog Feb 14 '13 at 17:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.