<p><strong>Recap:</strong></p>

<p>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$.</p>

<p>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.</p>

<p>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$.</p>

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

<p><strong>Answer:</strong></p>

<p>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.</p>

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

CC BY-SA 3.0
2013-09-29T03:03:43.840Z
2013-09-29T03:36:30.940Z
2013-09-29T03:36:30.940Z
mdxn
<p>I was reading up proof of Ladner's Theorem and I found this :</p>

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

<p>If SATH is NPC (which implies that SATH not in P) and $H(|x|)$ goes to inﬁnity, 
then SAT in P!</p>

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

<p>Repeat to solve SAT.</p>

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

CC BY-SA 3.0
2013-09-29T01:12:23.173Z
by self-reducibility, see the second proof [here](http://blog.computationalcomplexity.org/media/ladner.pdf). 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.
Kaveh
CC BY-SA 3.0
2013-09-29T09:50:54.553Z
What is "|$\mathrm{pad}|=|x',|x|^{H(|x|)}$" supposed to say?
David Richerby
<cc.complexity-theory><complexity-classes>
Ladner's Theroem Proof
Prashant
# Ladner's Theroem Proof

(Asked by: username_0 on 2013-09-29)

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 inﬁnity,
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.

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: by self-reducibility, see the second proof [here](http://blog.computationalcomplexity.org/media/ladner.pdf). 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.  
> **username_2**: What is "|$\mathrm{pad}|=|x',|x|^{H(|x|)}$" supposed to say?  

---

## 1 answers

### Answer by username_3 on 2013-09-29. Score: 4 | Accepted answer

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


---

