Unique-SAT — Jemoka Knowledge Base

Consider UNIQUE-SAT: for each version of SAT, UNIQUE-SAT has the property that we have either… no satisfying assignments exactly one satsifying assignments We thought that this was esaier than norm SAT, but turns out its exactly as hard. Valiant-Vazirani Insights: UNIQUE-SAT isn’t actually easier than SAT (if randomness is allowed). That is:

\begin{equation} \exists \text{rand. poly reduction } \text{SAT} \to \text{UNIQUE-SAT} \end{equation}

Given a n-variable circuit C where our goal is to decide if #C \geq 1 , we can efficiently produce circuits C^{(1)},…, C^{(t)} such that… a. if C is UNSAT, then C_1, …, C_{t} are all unsat b. if #c \geq 1, then with probability \geq \frac{2}{3}, ∃ j ∈ \left[\right] For possiblity of \#C organized into the following bucket \left[2^{k}, 2^{k+1}-1\right] = 0, 1, 2\to 3, 4\to 7, …, 2^{k} \to 2^{k+1}-1, 2^{k}, chosoe a random hash from a pairwise indenedent hash family:

\begin{equation} \mathcal{H} = \left\{h: \left\{0,1\right\}^{h} \to \left\{0,1\right\}^{k+2}\right\} \end{equation}

Assume for now \#c \geq 1, and call the “correct” bucket (i.e., #c lives in) [2^{k}, 2^{k+1}-1]. Consider now the cricuit:

\begin{equation} C^{(k)} \left(x\right) = C\left(x\right) \wedge \mathbb{1}\left[h_{k}\left(x\right) = 0\right] \end{equation}

Look! C^{(k)} have fewer satsifiying assignments than C. Each statsfying assignment stays satsified with probability \left(\frac{1}{2}\right)^{k+2} = p. The expected number of satsifying assignments of C^{(k)} is:

\begin{equation} \mathbb{E}_{h_{k} \sim \mathcal{H}_{k}} \left[#C^{(k)}\right] = p |s| = \left[\frac{1}{4}, \frac{1}{2}\right] \end{equation}

Now, let us consider the following lemma #+begin_proof Consider the following facts: \begin{align} &\mathbb{1}\left[#c(k) ≥ 1\right] ≤ ∑x ∈ Snil \mathbb{1}\left[x\text{ survives}\right] &\text{Pr} \left[#C(k) ≥1 a ≤ p |S|\right] \end{equation} snoatehu 1sntoaeu snteoauh oanetuh oeanuth #+end_proof Randomized Reduction …see above