How is a witness found in a proof of $\mathsf{NP} \subseteq \mathsf{P}/\log \implies \mathsf{P} = \mathsf{NP}$?

Question

I'm having a hard time understanding the actual proof of this proposition:

$\qquad \mathsf{NP} \subseteq \mathsf{P}/\log \implies \mathsf{P} = \mathsf{NP}$

The sketch of the proof is on slides 6-8 of this PDF.

So I let $L \in \mathsf{NP}$. That means that there's a deterministic polynomial-time TM $M^1_L$ s.t. $x \in L \iff \exists w. M^1_L(x,w) = 1$. I now need to construct a deterministic poly-time TM $M^2_L$ s.t. $x \in L \iff M^2_L(x) = 1$.

Looking at the proof in the slides above, I realize that given $x\in\{0,1\}^n$, $M^2_L$ needs to somehow find a witness $w$ for $x$ and then simply return whatever $M^1_L(x,w)$ does. But how do I find that witness?

Answer 1

Let's consider an $\mathsf{NP}$-complete like $SAT$: given a formula $\varphi$, is there a turht assignment $\tau$ such that $\tau \vDash \varphi$?

By assumption $\mathsf{NP} \subseteq \mathsf{P/\log}$ we know that $SAT \in \mathsf{P/\log}$. We will show that $SAT \in \mathsf{P}$ which will imply $\mathsf{NP} \subseteq \mathsf{P}$.

---

Notations

Let us denote a partial truth assignment as a function from the set of variables to $\mathbb{B}_\bot = \{1,0,\bot\}$ where $\bot$ means the corresponding variable is not determined. We will denote the empty assignment where all variables are left undetermined as $[]$ and the assignment that sets only the value of the variable $x$ to $b$ as $[x\mapsto b]$. Let $FV(\varphi)$ denote the set of free variables in $\varphi$. Let us also denote the formula resulting from pluging in the values from a partial truth assignment $\sigma$ into a formula $\varphi$ as $\varphi\sigma$.

---

Witness Search Problem: $SATSearch$

Consider the witness search problem $SATSearch$: given a formula $\varphi$, find a truth assignment $\tau$ s.t. $\tau \vDash \varphi$ if there is one, otherwise return $None$.

It is easy to see that if the witness search problem can be solved in deterministic polynomial-time then $SAT$ is in $\mathsf{P}$: we just run $SATSearch$ on $\varphi$ and $\sigma = \emptyset$ and we accept iff the answer is not $None$.

Also note that if $SAT \in \mathsf{P/\log}$, then so is $SATSearch$: consider the following polynomial time algorithm for $SATSearch$ that uses $SAT$ as a black box:

$\tau = []$
if not $SAT(\varphi\tau)$ return $None$
for $x \in FV(\varphi)$

• if $SAT(\varphi(\tau \cup [x \mapsto 0]))$ then $\tau = \tau \cup [x \mapsto 0]$
• else $\tau = \tau \cup [x \mapsto 1]$

return $\tau$

More generally the claim holds for any class which is closed under Cook reductions.

---

By our assumption $SATSearch\in \mathsf{P/\log}$. Let $M$ be an TM with polynomial running time and advice of length $l(n)=O(\log n)$ where $n$ is the size of the input formula $\varphi$. We show that $SATSearch$ can be solved in deterministic polynomial time.

for all c of length $l(|\varphi|)$

• $\tau = M(\varphi,c)$
• if $\tau \vDash \varphi$ then return $\tau$

return $None$

If $\varphi$ is satisfiable, then at least for the right advice $M$ will return a witness and we can verify it. If the formula is not satisfiable, no $\tau$ can satisfy $\varphi$ so we will return $None$.

The running-time of the algorithm is polynomial and it uses no advice. So $SATSearch$ can be solved in deterministic polynomial time with no advice.

Therefore we can conclude that $\mathsf{NP}=\mathsf{P}$ if $\mathsf{NP}\subseteq \mathsf{P/\log}$.

Answer 2

Here's a sketch of my proof:

It is enough to show that $\mathsf{SAT}\in \mathsf{P}$. Since $\mathsf{SAT}\in \mathsf{NP}$, by our assumption, $\mathsf{SAT}\in\mathsf{P}/\log$.

This means that there exists a sequence of advices $\{a_n\}_{n\in\mathbb{N}}$ such that $|a_n|\le \log(n)$, and a polynomial-time DTM $M$ such that for all $x\in\{0,1\}^n$, $M(x,a_n) = 1 \iff x \in \mathsf{SAT}$.

We can use this DTM to construct another polynomial-time DTM $M_1$ that takes as input $x\in\{0,1\}^n$ (an encoding of some CNF formula $\varphi(x_1,\ldots,x_m)$) and an advice string $|a|\le \log(n)$ and generates a candidate for a witness for $x$ the following way:

1. Verify that $\varphi$ is satisfiable by checking that $M(x,a)=1$, reject otherwise.

2. For $i = 1$ to $m$ do

   Run $M(\varphi(\ldots,x_i=0,\ldots),a)$ and $M(\varphi(\ldots,x_i=1,\ldots),a)$, Whichever returns 1 is a correct assignment, so output the corresponding value of $x_i$, and modify the formula $\varphi$ with that assignment for the next iteration...

It's easy to see that $M_1$ runs in polynomial-time and does indeed produce a correct witness if it exists, and if the advice given was the correct one.

Now, the last step of the proof is to use a deterministic poly-time verifier $M_V$ for $\mathsf{SAT}$ (one exists because it's in $\mathsf{NP}$) and create a deterministic poly-time decider for it. We can do this easily, because since the length of the advice is $\log(n)$, there can be at most $2^{\log(n)}=n$ advices, meaning that we can simply create a loop from $i = 0$ to $n-1$ and in every iteration generate a witness $w = M_1(x,i)$ and then test it with our verifier: $M_V(x,w)$.

We accept only if one of the witnesses match, and reject if none do.