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

ignougroup
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 $xin{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 $[xmapsto 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 $varphisigma$.

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(varphitau)$ 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 $SATSearchin 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