P, NP, coNP, and Polynomial Reductions

Assume item 1. By [L1], choose a verifier relation $R$ and a polynomial certificate bound $p$. Let $D_R$ be a deterministic polynomial-time decider for the paired language $L_R=\{⟨x,u⟩:(x,u)\in R\}$. Build a nondeterministic machine $N$ that, on input $x$, first guesses a binary word $u$ of length at most $p(\mathrm{\mid }x\mathrm{\mid })$ and then runs $D_R$ on $⟨x,u⟩$, accepting exactly when $D_R$ accepts. Because every branch chooses at most $p(\mathrm{\mid }x\mathrm{\mid })$ guessed bits and then performs one polynomial-time deterministic verification, every branch halts within polynomial time. Since $x\in L$ exactly when some certificate $u$ makes $(x,u)\in R$, the machine $N$ accepts exactly the words of $L$. Thus item 2 holds.

Assume item 2. By [L2], fix a nondeterministic machine $N$ and an exponent $k$ such that every branch on inputs of length $n$ halts within $c{n}^k$ steps for some constant $c$. Let $b$ be the maximum number of available nondeterministic choices in any one local configuration of $N$, and choose an integer $r\ge 1$ with $2^r\ge b$. An accepting branch is then determined by a finite sequence $d_1,\dots ,d_t$ of at most $c{n}^k$ choice numbers from $\{0,\dots ,b-1\}$. Encode that sequence as the binary word $u:=1^{t}0{\beta }_1\cdots {\beta }_t,$ where each ${\beta }_i$ is the $r$-bit binary expansion of $d_i$. The initial unary header recovers $t$, and then the decoder reads exactly $t$ consecutive blocks of length $r$, so this branch description is effectively decodable.

Define a deterministic verifier for $L$ as follows. On input $⟨x,u⟩$, first decode $u$ by reading its unary header and then the declared number of $r$-bit choice blocks; reject malformed encodings. Next simulate $N$ on $x$ while forcing those choices in order, reject if the certificate requests a nonexistent choice or ends before acceptance, and accept exactly when the forced run ends in an accepting state after consuming the full encoded branch description. Step 1.2 guarantees that $x\in L$ yields some accepting-branch certificate, and any accepting certificate describes a genuine accepting branch. The certificate length is polynomial in $\mathrm{\mid }x\mathrm{\mid }$ because it has one unary header bit per simulated choice and each choice uses the fixed block length $r$, with at most $c{n}^k$ choices. The verifier runtime is therefore polynomial in $\mathrm{\mid }x\mathrm{\mid }+\mathrm{\mid }u\mathrm{\mid }$ because it only decodes $u$ and replays that many steps of $N$. Therefore item 1 holds by [L1].

Steps 1.1 and 2.1 prove both directions, so the verifier and nondeterministic definitions of NP agree. The lower bound in [L3] is compatible with these polynomial bounds: reading the whole input and certificate is already only linear in their lengths.

By [L1], choose a polynomial-time decider $D$ for $L$. Use the empty certificate $u=\epsilon$ and define the verifier relation $R_L$ by $(x,\epsilon )\in R_L$ exactly when $D$ accepts $x$, with no other certificates allowed. Then the paired language for $R_L$ is decidable in polynomial time by running $D$ on the first component and checking that the second component is empty. Thus [L2] gives $L\in NP$.

Swap the accepting and rejecting halting states of $D$ to obtain a polynomial-time decider for the complement $\{0,1{\}}^{\ast }\setminus L$. Repeating step 1.1 with the same empty-certificate idea shows that the complement belongs to $NP$. Therefore [L3] gives $L\in coNP$.

Steps 1.1 and 2.1 show that every language in $P$ lies in $NP\cap coNP$.

Define $h:=g\circ f$. Because both $f$ and $g$ are total by [L1], the composite $h$ is also total.

For every source word $x$, [L1] gives $x\in A⟺f(x)\in B⟺g(f(x))\in C$. So $x\in A⟺h(x)\in C$.

The function $f$ runs in polynomial time and can output only polynomially many symbols, so the length of $f(x)$ is polynomially bounded in $\mathrm{\mid }x\mathrm{\mid }$. Running $g$ on that output therefore still takes polynomial time in $\mathrm{\mid }x\mathrm{\mid }$. Hence $h$ is a polynomial-time many-one reduction from $A$ to $C$.

Assume $B\in P$, and let $D_B$ be a polynomial-time decider for $B$ from [L3]. On input $x$, compute the fixed map $f(x)$ and then run $D_B$ on that output. By [L1], the answer is correct because $x\in A$ iff $f(x)\in B$, and the whole procedure is polynomial-time because both stages are. Thus $A\in P$.

Assume $B\in NP$. By [L4], choose a verifier relation $R_B$ and polynomial certificate bound $p$ for $B$. Using the fixed reduction map $f$, define a verifier for $A$ by declaring that $(x,u)$ is accepted exactly when $(f(x),u)\in R_B$. The output length $\mathrm{\mid }f(x)\mathrm{\mid }$ is polynomial in $\mathrm{\mid }x\mathrm{\mid }$, so the bound $p(\mathrm{\mid }f(x)\mathrm{\mid })$ is still polynomial in $\mathrm{\mid }x\mathrm{\mid }$. Correctness follows from $x\in A⟺f(x)\in B⟺\mathrm{\exists }u\text{ with }\mathrm{\mid }u\mathrm{\mid }\le p(\mathrm{\mid }f(x)\mathrm{\mid })\text{ and }(f(x),u)\in R_B$. Therefore $A\in NP$.

Assume $B\in coNP$. Then $B^c\in NP$ by [L5]. The fixed reduction map $f$ also witnesses $A^c{\le }_p{B}^c$, because $x\in A^c⟺x\mathrm{\notin }A⟺f(x)\mathrm{\notin }B⟺f(x)\in B^c$. Applying step 1.2 to the reduction $A^c{\le }_p{B}^c$ gives $A^c\in NP$, and then [L5] yields $A\in coNP$. The composition principle [L2] guarantees that chaining such transfers remains inside the same reduction class.

Steps 1.1, 1.2, and 2.1 prove the three transfer clauses.

Let $L\in NP$ be arbitrary. By [L1], because $C$ is NP-hard, there is a polynomial-time many-one reduction $L{\le }_{p}C$. Then [L2] and the hypothesis $C\in P$ give $L\in P$.

Step 1.1 shows $NP\subseteq P$. By [L3], every language in $P$ also lies in $NP$, so $P\subseteq NP$. Therefore $P=NP$.

Query the $SAT$ oracle on $\phi$ itself. If the answer is "no", halt and report that no satisfying assignment exists. If the answer is "yes", initialize the current residual formula to ${\psi }_0:=\phi$.

For $i=1,\dots ,n$, form the two residual formulas obtained from ${\psi }_{i-1}$ by substituting $x_i=1$ and $x_i=0$. Query the oracle on the first one. If it is satisfiable, record $x_i=1$ and set ${\psi }_i$ equal to that first residual formula. Otherwise record $x_i=0$ and set ${\psi }_i$ equal to the second residual formula. At least one branch is satisfiable, because any satisfying assignment of ${\psi }_{i-1}$ gives one of the two values to $x_i$.

By induction on $i$, the maintained residual formula ${\psi }_i$ is satisfiable and is obtained from $\phi$ by fixing the first $i$ variables to the recorded values. After the final stage, every variable has been assigned, so the recorded bits form a satisfying assignment for $\phi$. This is exactly the witness demanded in [L1].

The algorithm makes at most $n+1$ oracle calls, and each intermediate substitution and formula rewrite is polynomial in $\mathrm{\mid }\phi \mathrm{\mid }$. Since the satisfying assignment itself has length $n\le \mathrm{\mid }\phi \mathrm{\mid }$, this stays within the polynomial witness regime of [L2]. Therefore SAT search polynomial-time Turing reduces to SAT decision.

To prove $NP\subseteq PSPACE$, let $L\in NP$. By [L1], choose a verifier for $L$ with runtime bounded by a polynomial $q(n)$ and certificate length bounded by a polynomial $p(n)$. A deterministic decider for $L$ can enumerate all certificates $u$ of length at most $p(\mathrm{\mid }x\mathrm{\mid })$ in lexicographic order, run the verifier on $(x,u)$, and accept as soon as one certificate succeeds. It stores only the input $x$, the current certificate $u$, and the verifier workspace, so the total space used is polynomial in $\mathrm{\mid }x\mathrm{\mid }$. Hence $L\in PSPACE$ by [L2] and [L3].

To prove $PSPACE\subseteq EXP$, let $L\in PSPACE$. Then by definition there exists $k\ge 1$ and a deterministic machine $M$ deciding $L$ while using at most $c{n}^k$ tape cells on inputs of length $n$, for some constant $c$. Fix such an input length $n$. Because of [L5], a configuration of $M$ is determined by one of finitely many states, the head positions on the finitely many tapes, and the contents of at most $c{n}^k$ visited cells. Therefore the total number of possible configurations is at most $\mathrm{\mid }Q\mathrm{\mid }\cdot (c{n}^k+1{)}^d\cdot \mathrm{\mid }\mathrm{\Gamma }{\mathrm{\mid }}^{dc{n}^k}=2^{O(n^k)}$ for a constant $d$ depending only on the fixed number of tapes.

Since $M$ is deterministic and halts on every input, it cannot visit the same configuration twice on one accepting or rejecting run: a repeated configuration would force an infinite loop from that point onward. So the running time on inputs of length $n$ is bounded by the number of reachable configurations from step 1.2, hence by $2^{O(n^k)}$. Enlarging the exponent if necessary, there exists $m$ with $2^{O(n^k)}\le 2^{n^m}$ for all sufficiently large $n$. Therefore $L\in EXP$ by [L2] and [L4].

Steps 1.1 and 2.1 prove $NP\subseteq PSPACE\subseteq EXP$.

By [L1], any language already known to be in $P$ is automatically also in $NP$.

Step 1.1 contradicts the slogan in the statement: a polynomial-time solvable language can still belong to $NP$. By [L2], NP is about efficiently verifiable yes-certificates, not about being known outside polynomial time.

The definition quoted in [L1] contains no clause asserting $C\mathrm{\notin }P$. It says only that $C$ is in $NP$ and is hard for $NP$ under the chosen reductions.

If $C\mathrm{\notin }P$ had already been proved, then [L1] would give a language in $NP\setminus P$ and hence prove $P\mathrm{\ne }NP$. But [F1] records that this question remains unsolved. Conversely, [L2] says that finding $C\in P$ would prove $P=NP$. Thus NP-completeness does not mean that exclusion from $P$ has already been proved; it identifies the consequence either kind of resolution would have.