# Sat is reducible to

﻿Keywords: sat is reducible to
Description: 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 idea of the

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 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.

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.

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.

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.