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

Problem Detail: 

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?

Asked By : Caleb

Answered By : Kaveh

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11223