Ladner's Theroem Proof

Question

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.

Answer 1

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