3
$\begingroup$

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?

$\endgroup$

migrated from cstheory.stackexchange.com Apr 11 '13 at 11:13

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 1
    $\begingroup$ The key is that if there is a $\lg n$ small circuit, we can do a brute-force search to find the circuit in poly-time for a given instance size and compute it in P. This works for a problem like SAT because we can use the self-reducibility of its search problem to make sure that the circuit we found solves the instance correctly for non-satisfiable instances (checking the correctness in satisfiable instances is easy as CircuitValue is in $\mathsf{P}$). This would not work for an arbitrary problem in $\mathsf{P}/1$ as we don't know how to verify that the circuit's answer is correct. $\endgroup$ – Kaveh Apr 8 '13 at 0:03
  • $\begingroup$ I thought that $L \in P/log$ meant that we have a sequence $\{a_n\}_{n\in\mathbb{N}}$ of advices of length at most $log(n)$, and a TM $M$ s.t. $M(x,a_n) = 1 \iff x \in L$ $\forall x\in\{0,1\}^n$. How do circuits enter the picture? Is this another definition of $P/log$? $\endgroup$ – Caleb Apr 8 '13 at 4:53
  • $\begingroup$ You can think of an advice as the description of a circuit (note that the description can be shorter than the circuit itself which is of polynomial size). But it doesn't matter, if you prefer the definition with advice, then we are brute-forcing to find the advice. $\endgroup$ – Kaveh Apr 8 '13 at 5:00
  • $\begingroup$ I think I see what you mean about the circuits now. Given the definition of $P/log$ that was on slide 4: $P/log = \bigcup_{c,k>0} DTIME(kn^c)/k log(n)$ we can show that $P/log = \bigcup_c SIZE(log(n^c))$ in pretty much exactly the same way that $P/poly = \bigcup_c SIZE(n^c)$. I can't seem to wrap my head around as to how we are brute-forcing this advice. I realize that since its length is at most $log(n)$, so that means that for a particular $n$ we need to test at most $n$ advices. But in the loop that generates advices, I can't just check $M(x,a)=1$ as that might give false-positives. $\endgroup$ – Caleb Apr 8 '13 at 5:10
  • 1
    $\begingroup$ The circuits are still polynomial size. But the can be described with $\lg n$ bits which is the advice. $\endgroup$ – Kaveh Apr 8 '13 at 10:52
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I ended up accepting your proof over mine, because I think there might be a problem in it. Do you mind taking a look at it? $\endgroup$ – Caleb Jul 26 '13 at 5:57
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think there is a problem in the proof, I wrote an algorithm for SATSearch that uses an advice (the machine $M_1$), but I think it's wrong because when it calls $M$ with a formula that had a partial truth assignment (so it might have a different length from the original formula) and yet it uses the same advice which might not work for the new length of the formula. Is my proof salvageable? Can I somehow pad the formula so it's the same length even after the partial truth assignment? $\endgroup$ – Caleb Jul 26 '13 at 6:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.