Read-back: PvsNP.P_eq_NP_of_npComplete_mem_P

Throughout, $\Sigma = \{\mathsf{false}, \mathsf{true}\}$ is the two-letter Boolean alphabet, $\Sigma^*$ is the set of all finite lists (strings) of Booleans, including the empty string, and $|w|$ is the length of a string $w$. A language is any subset $L \subseteq \Sigma^*$ (there is no restriction whatsoever on $L$: it may be empty, all of $\Sigma^*$, or undecidable). The two classes $\mathbf{P}$ and $\mathbf{NP}$ appearing in the statement are specific sets of such languages over $\Sigma$, defined below by way of a specific machine model; languages over any other alphabet do not appear.

The statement. For every language $L \subseteq \Sigma^*$, if

1. $L$ is "NP-complete" in the sense spelled out below, namely $L \in \mathbf{NP}$ and every $L' \in \mathbf{NP}$ is polynomial-time many-one reducible to $L$ (in the sense below), and
2. $L \in \mathbf{P}$ (in the sense below),

then the two sets of languages are equal:

$$\mathbf{P} = \mathbf{NP},$$

i.e. for every language $M \subseteq \Sigma^*$, $M \in \mathbf{P}$ if and only if $M \in \mathbf{NP}$. The statement is a conditional: if no language satisfies both hypotheses 1 and 2 simultaneously, it asserts nothing. Neither $\mathbf{P} \subseteq \mathbf{NP}$ nor any other relation between the classes is assumed; the conclusion is full set equality.

The machine model (what "computable in polynomial time" means everywhere below). All computability notions are phrased through one notion, "there exists a polynomial-time stack machine computing $f$ with respect to input encoding $e_{\mathrm{in}}$ and output encoding $e_{\mathrm{out}}$", where $f : A \to B$, $e_{\mathrm{in}} : A \to \Gamma_{\mathrm{in}}^*$ and $e_{\mathrm{out}} : B \to \Gamma_{\mathrm{out}}^*$ are arbitrary functions (the encodings are not required to be injective or decodable; they are just functions to lists). This notion means that the following data exist (the existence is all that is used; the specific machine is not fixed):

• A machine $T$ consisting of: a finite set $K$ of stack indices (with decidable equality) and two designated indices $k_0$ (input stack) and $k_1$ (output stack), which are allowed to coincide; for every $k \in K$ a type $\Gamma_k$ of symbols that may be stored on stack $k$, where only $\Gamma_{k_0}$ is required to be finite (the alphabets of the other stacks may be arbitrary, possibly infinite, types); a finite set $\Lambda$ of program labels with a designated main label; a finite set $S$ of internal states with a designated initial state $s_0$; and a program assigning to each label a statement. A statement is a finite tree built from the operations: push onto stack $k$ a symbol computed from the internal state; peek at the top of stack $k$ (possibly absent) and update the internal state accordingly; pop the top of stack $k$ (possibly absent) and update the internal state accordingly; replace the internal state by a function of itself; branch on a Boolean function of the internal state; ending either in "go to the label computed from the internal state" or in "halt".
• A bijection between $\Gamma_{k_0}$ and $\Gamma_{\mathrm{in}}$ and a bijection between $\Gamma_{k_1}$ and $\Gamma_{\mathrm{out}}$.
• A polynomial $p$ in one variable with natural-number coefficients (any such polynomial, including constants).
• A proof that for every input $a \in A$ there is a number of steps $s \le p\bigl(|e_{\mathrm{in}}(a)|\bigr)$ such that, starting from the initial configuration (current label $=$ main, internal state $= s_0$, stack $k_0$ holding the list $e_{\mathrm{in}}(a)$ transported through the bijection with the first symbol on top, and every other stack empty), after exactly $s$ applications of the one-step transition the machine is in the halting configuration determined by $e_{\mathrm{out}}(f(a))$, namely: no current label (halted), internal state equal to the initial state $s_0$ again, stack $k_1$ holding the list $e_{\mathrm{out}}(f(a))$ transported through the bijection, and every other stack empty (so, when $k_0 \ne k_1$, the input stack must have been completely emptied). One step is the execution of the entire statement attached to the current label (all of its pushes, pops, peeks, loads and branches, however many, count as a single step); the count $s$ is the number of such label-executions. The time bound is a function of the length of the encoded input $e_{\mathrm{in}}(a)$, not of $a$ itself.

The functions $f$ involved are always total, so a machine as above halts on every input in the required form.

The class $\mathbf{P}$. $L \in \mathbf{P}$ means: there is a total function $\chi : \Sigma^* \to \Sigma$ such that

• there exists a polynomial-time stack machine (as above) computing $\chi$ with input encoding the identity $w \mapsto w$ (so $\Gamma_{\mathrm{in}} = \Sigma$ and the time bound is $p(|w|)$) and output encoding $b \mapsto [b]$, the one-symbol list (so $\Gamma_{\mathrm{out}} = \Sigma$ and the output stack must hold exactly the single symbol $\chi(w)$ at halting); and
• for every $w \in \Sigma^*$: $w \in L \iff \chi(w) = \mathsf{true}$.

The class $\mathbf{NP}$. $L \in \mathbf{NP}$ means: there exist a total function $R : \Sigma^* \times \Sigma^* \to \Sigma$ and a natural number $k \ge 0$ such that

• there exists a polynomial-time stack machine computing $R$ with input encoding

$$(x, y) \longmapsto \bigl[\mathrm{inl}(x_1), \dots, \mathrm{inl}(x_{|x|}),\ \mathrm{inr}(y_1), \dots, \mathrm{inr}(y_{|y|})\bigr]$$

over the four-symbol alphabet $\Gamma_{\mathrm{in}} = \Sigma \sqcup \Sigma$ (the symbols of $x$ tagged "left", followed by the symbols of $y$ tagged "right"; the encoded length is $|x| + |y|$, so the time bound is $p(|x|+|y|)$), and output encoding $b \mapsto [b]$; and

• for every $w \in \Sigma^*$:

$$w \in L \iff \exists\, y \in \Sigma^* \text{ with } |y| \le |w|^{k} \text{ and } R(w, y) = \mathsf{true}.$$

Here $|w|^k$ is ordinary natural-number exponentiation with $|w|^0 = 1$ (also $0^0 = 1$); in particular $k = 0$ is allowed (then $|y| \le 1$), and for $k \ge 1$ and $w$ the empty string the only admissible witness is the empty string. The checker $R$ must be computed within time $p(|w|+|y|)$ on all pairs, including those with $|y| > |w|^k$. The exponent $k$ is one fixed number for the language, but is otherwise arbitrary.

Polynomial-time reducibility. For languages $L_1, L_2 \subseteq \Sigma^*$, "$L_1$ is polynomial-time reducible to $L_2$" means: there is a total function $f : \Sigma^* \to \Sigma^*$ such that

• there exists a polynomial-time stack machine computing $f$ with both input and output encodings the identity on $\Sigma^*$ (so $\Gamma_{\mathrm{in}} = \Gamma_{\mathrm{out}} = \Sigma$, the time bound is $p(|x|)$, and at halting the output stack holds exactly the string $f(x)$); no bound on $|f(x)|$ is stated other than what this implies; and
• for every $x \in \Sigma^*$: $x \in L_1 \iff f(x) \in L_2$.

NP-completeness. "$L$ is NP-complete" means: $L \in \mathbf{NP}$, and for every language $L' \subseteq \Sigma^*$ with $L' \in \mathbf{NP}$, $L'$ is polynomial-time reducible to $L$ in the sense just given.

Summary in one sentence. For any set $L$ of Boolean strings, if $L$ belongs to $\mathbf{NP}$ (as defined above via a checker $R$, a witness-length exponent $k$ and a polynomial-time stack machine), every member of $\mathbf{NP}$ many-one reduces to $L$ via a function computed by a polynomial-time stack machine with identity encodings, and $L$ also belongs to $\mathbf{P}$ (decided by a polynomial-time stack machine with identity input encoding and one-symbol output), then the set $\mathbf{P}$ and the set $\mathbf{NP}$ of languages over $\Sigma$ are one and the same set.