Suggest edit — Unique-SAT

Title

Name

Note

---
title: "Unique-SAT"
type: concept
source: https://www.jemoka.com/posts/kbhunique_sat/
confidence: high
status: active
---

Consider UNIQUE-SAT:
for each version of SAT, UNIQUE-SAT has the property that we have either&hellip;
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&rsquo;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)},&hellip;, C^{(t)}$ such that&hellip;
a. if $C$ is UNSAT, then $C_1, &hellip;, C_{t}$ are all unsat b. if $#c \geq 1$, then with probability $\geq \frac{2}{3}$, $∃ j ∈ \qty [] $
For possiblity of $\#C$ organized into the following bucket $\qty [2^{k}, 2^{k+1}-1] = 0, 1, 2\to 3, 4\to 7, &hellip;, 2^{k} \to 2^{k+1}-1, 2^{k}$, chosoe a random hash from a pairwise indenedent hash family:
\begin{equation} \mathcal{H} = \qty {h: \qty {0,1}^{h} \to \qty {0,1}^{k+2}} \end{equation}
Assume for now $\#c \geq 1$, and call the &ldquo;correct&rdquo; bucket (i.e., $#c$ lives in) $[2^{k}, 2^{k+1}-1]$. Consider now the cricuit:
\begin{equation} C^{(k)} \qty(x) = C\qty(x) \wedge \mathbb{1}\qty [h_{k}\qty(x) = 0] \end{equation}
Look! $C^{(k)}$ have fewer satsifiying assignments than $C$. Each statsfying assignment stays satsified with probability $\qty(\frac{1}{2})^{k+2} = p$.
The expected number of satsifying assignments of $C^{(k)}$ is:
\begin{equation} \mathbb{E}_{h_{k} \sim \mathcal{H}_{k}} \qty [#C^{(k)}] = p |s| = \qty [\frac{1}{4}, \frac{1}{2}] \end{equation}
Now, let us consider the following lemma
#+begin_proof Consider the following facts:
\begin{align} &amp;\mathbb{1}\qty [#c(k) ≥ 1] ≤ ∑x ∈ Snil \mathbb{1}\qty [x\text{ survives}] &amp;\text{Pr} \qty [#C(k) ≥1 a ≤ p |S|] \end{equation}
snoatehu 1sntoaeu snteoauh oanetuh oeanuth #+end_proof
Randomized Reduction &hellip;see above