0
$\begingroup$

I was reading up proof of Ladner's Theorem and I found this :

$$\mathrm{SATH} = \{ (x,\mathrm{pad}) \mid x \in \mathrm{SAT} \text{ and } |\mathrm{pad}|=|x|^{H(|x|)}\}.$$

If SATH is NPC (which implies that SATH not in P) and $H(|x|)$ goes to infinity, then SAT in P!

Proof: Suppose $f(x) = (x',\mathrm{pad})$, such that $|(x',\mathrm{pad})| \leq c|x|^c$. If $|x'|>|x|/2$, then $|\mathrm{pad}| = |x',|x|^{H(|x|)} > c|x|^c$ (for long enough $x$). So $|x'|$ is at most $|x|/2$.

Repeat to solve SAT.

What does it mean to repeat and solve sat? How does this make SAT in P.

$\endgroup$
  • 2
    $\begingroup$ by self-reducibility, see the second proof here. ps: when posting a question about a proof provide either a link to it or give a reference so the readers can check the proof in the source. $\endgroup$ – Kaveh Sep 29 '13 at 1:12
  • $\begingroup$ What is "|$\mathrm{pad}|=|x',|x|^{H(|x|)}$" supposed to say? $\endgroup$ – David Richerby Sep 29 '13 at 9:50
4
$\begingroup$

Recap:

At this stage in the proof of Ladner's Theorem, it has already been shown that $H(n)$ tends towards $\infty$ as $n$ does. You are assuming that $\text{SAT}_H$is $\text{NP-complete}$ for the sake of contradiction. Equivalently: $\text{SAT} \le_p \text{SAT}_H$.

The mapping used in the reduction, $f(x)$, maps $\langle \varphi , pad \rangle$ to a $\langle \varphi' , pad \rangle$. Because of the polynomial time limitation, $\langle \varphi' , pad \rangle$ has to be, at most, of size $c\left|\langle \varphi , pad \rangle\right|^c$. If the size of $\varphi$ remains unchanged, then the length of the padding causes $\langle \varphi' , pad \rangle$ to be too large.

The only alternative is to assume that $f(x)$ somehow reduces the size of $\varphi$ to compensate for possible growth of the padding. It is pointed out that size of $\varphi'$ is less than or equal to $\left|\varphi\right|/2$.

The primary observation here is that $f(x)$ has significantly reduced the size of the $\varphi$ we need to consider in polynomial time.

Answer:

Take padding out of the picture completely and just consider instances of $\text{SAT}$ (with formula $\varphi$). Take a modification of $f$ to ignore padding and compose it $\text{log}_2(\left|\varphi\right|)$ times on our input $\varphi$. The result is a boolean formula, $\varphi^*$, of constant size that is satisfiable if and only if $\varphi$ is. The satisfiability of $\varphi^*$can trivially be determined in far less than polynomial time. So overall, this entire procedure must decide any $SAT$ instance in polynomial time.

Because this violates Ladner's assumption that $\text{P} \ne \text{NP}$, $\text{SAT}_H$ could not possibly be $\text{NP-complete}$.

$\endgroup$

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.