betaFeedback

WorksMathematics

A negative answer to the final question in "Les petits cailloux"

Abstract

We consider polynomial-time computation over arbitrary structures, with unit cost for the primitive operations and relations and with nondeterministic witnesses consisting of arbitrary structure elements. We prove that every finite-signature structure with two distinct available elements and containing a binary operation ∗* and total unary operations L,RL,R such that L(x∗y)=xL(x*y)=x and R(x∗y)=yR(x*y)=y satisfies P≠NPP\ne NP. The proof encodes an exponentially long computation in one element. An incorrect transition has a polynomial-size binary address, and hence the existence of an error is an NBPNBP problem. Existence of a correct accepting trace belongs to the mixed second level Σ2S,BΣ_2^{S,B}, with an arbitrary-element existential block followed by a binary universal block. We obtain EXP⊆Σ2S,B⊆PHEXP\subseteqΣ_2^{S,B}\subseteq PH. A hypothetical equality P=NPP=NP would collapse this hierarchy to PP and imply P=EXPP=EXP, contradicting a direct deterministic diagonalization over the same structure. A simulation by function graphs extends the obstruction to every jointly injective binary primitive under the same assumptions on equality and available elements. Consequently no unary predicate on Malcev's free binary-tree algebra yields P=NPP=NP, with or without the projections. In contrast, starting from the author's unary example, we construct five infinite structures with binary operations and P=NPP=NP. These include an algebra with one binary operation and one constant, an expansion with an associative rectangular-band operation, and an algebra with one binary operation whose every row and column has infinite image.

Introduction

The model of computation introduced by Blum, Shub and Smale permits exact operations on real numbers at unit cost and gives structure-dependent versions of the usual complexity classes [1]. The monograph of Blum, Cucker, Shub and Smale develops this approach systematically [2]. Goode extended the foundational study of computation from rings to arbitrary structures [9]. Poizat’s Les petits cailloux places it in a model-theoretic setting: the computational universe is a first-order structure, the available elementary operations and tests are its functions and relations, and the length of an input is the number of its components [19]. One may therefore ask whether a particular infinite structure satisfies P=NPP = NP as a structure-relative question, distinct from the corresponding question for finite-alphabet Turing machines.

The choice of primitives matters. Meer studied restricted real machines and obtained separation results for suitable operation sets [17, 18]; Koiran analyzed computation with addition and order [12]. Fournier and Koiran subsequently compared lower-bound questions for additive real computation with their classical finite-alphabet counterparts, distinguishing the parameter-free and arbitrary-parameter settings [6]. These works show why a statement about PP and NPNP over one signature cannot be transferred to another merely because the underlying set is unchanged. They also motivate the explicit treatment of constants and permitted instructions below.

In the general model-theoretic setting, the question whether an infinite structure of finite signature can satisfy P=NPP = NP has a positive answer. Hemmerling constructed suitable expansions of structures on binary words [11], and Gaßner gave related constructions [7]. The author constructed a structure with three unary functions and a unary predicate in which existential satisfaction with arbitrary parameters is decidable in polynomial time [21]. The connection between this property and fast elimination of quantifiers is explained in [22]. The latter condition concerns a uniform decision procedure, or equivalently appropriate circuits; it does not require an explicitly written equivalent quantifier-free formula of polynomial length.

The construction in [21] develops Poizat’s use of a truth predicate on a unary successor structure. In Poizat’s earlier construction, an existential formula with one free variable is represented by a term whose truth is read by the predicate [20]. Unary terms cannot combine an arbitrary tuple of independent parameters into one element. The author’s construction overcomes this limitation by computing finite local information about the parameter tuple and consulting a predicate that encodes suitable sentences. We recall this existence theorem in Section 5, without repeating the proof.

There remains a distinct proposal: use the binary operation of Malcev’s free tree algebra to combine parameters, and expand that algebra by a truth predicate. We consider the following precise version of Poizat’s question, in the framework of [19, 20]; the specific Malcev proposal is recalled in [22 p. 465].

Question 1.1 (Les petits cailloux). Let M\mathcal{M} be the algebra of finite binary trees, with the operation x∗yx * y forming a new root with left subtree xx and right subtree yy, and with two distinct named elements 0,10, 1. Does there exist a unary predicate VV such that the resulting structure satisfies P=NPP = NP for unit-cost computation?

We answer this question negatively. The result holds whether the left and right projections are primitive operations or are omitted. More generally, a finite-signature structure with two distinct available elements and a jointly injective binary primitive cannot satisfy P=NPP = NP. The obstruction persists after adding any finitely many further operations or relations. It is therefore independent of the particular method proposed for constructing VV. Our second running example is standard arithmetic N=(N;+,⋅,0,1)\mathcal{N} = (\mathbb{N}; +, \cdot, 0, 1). Cantor pairing and its two projections are first-order definable in this original signature. A simulation by their graphs transfers the obstruction to every finite expansion of N\mathcal{N}, in particular to (N;+,⋅,0,1,V)(\mathbb{N}; +, \cdot, 0, 1, V) for every unary predicate VV. Section 4.2 compares the resulting restriction on existential truth predicates with Tarski’s undefinability theorem. Section 4.2.2 then treats the signature consisting of addition, remainder, and base-two exponentiation. In that language the pairing and projections are fixed term functions, giving an unconditional trace inclusion and a quantifier-free diagonal obstruction under elementary syntax coding.

The reason is computational. With a pairing function and its projections, one structure element can encode any prescribed finite list of configurations, including an exponentially long list. An individual entry is accessible by a binary address of polynomial length. Thus a nondeterministic polynomial-time machine can find an error in the proposed computation. If P=NPP = NP, the absence of errors can be checked deterministically in polynomial time. Guessing the whole trace as one element then makes every deterministic exponential-time computation an NP computation, and the assumed collapse makes it polynomial-time. A universal-machine diagonalization excludes this conclusion. Section 2.3 defines the full and mixed polynomial hierarchies, and Lemma 3.4 locates the trace condition precisely in Σ2S,B\Sigma^{S,B}_2.

The local checking of a computation is in the tradition of Cook’s satisfiability construction [5]. Its existential trace and universally checked positions also have the form familiar from alternating computation [4]. The extra feature used here is specific to the structure model: the entire trace is a single permissible nondeterministic witness, however large its external representation. Related difficulties concerning compressed oracle encodings occur in Gaßner’s work [8]. Gaßner also observes that, in her earlier construction on binary trees, equality of trees is not available as a one-step test [8 p. 1204]. Equality is a primitive test throughout the present paper. We give the full argument, including the structure-relative hierarchy proof, so that no transfer of a classical theorem is left implicit.

The negative result does not exclude all binary operations. Starting from the unary structure A\mathcal{A} of [21], we construct structures B,C,D,E,F\mathcal{B},\mathcal{C},\mathcal{D},\mathcal{E},\mathcal{F} with P=NPP = NP. One of them has just one binary operation and one constant, with no primitive predicate. Another has an associative idempotent binary operation, and a further example has one binary operation with infinite image in every row and every column. Each construction is stated as a corollary with a separate simulation proof.

Computation and satisfaction over a structure

The free Malcev algebra and standard arithmetic

Definition 2.1 (The Malcev algebra freely generated by a set). Let GG be a nonempty set. The universe TGT_G consists of all finite rooted ordered full binary trees whose leaves are labelled by elements of GG. Equivalently, it is the set of formal terms generated by the rules

g∈TG(g∈G),u,v∈TG⟹(u∗v)∈TG.g \in T_G \quad(g \in G), \qquad u,v \in T_G \Longrightarrow(u * v) \in T_G.

Different generators denote different elements, no generator is a product, and

u∗v=u′∗v′⟺u=u′ and v=v′.u * v = u' * v' \Longleftrightarrow u = u' \text{ and } v = v'.

The operation ∗* forms a new root with the two given trees as its ordered subtrees. The algebra (TG;∗)(T_G; *) is the free Malcev algebra on GG, also called the free magma on GG: every map from GG to an algebra with one binary operation extends uniquely to a homomorphism from TGT_G, by recursion on finite terms. This is the case of a single binary operation among the absolutely free algebras studied by Malcev [14 p. 730]. Here “Malcev algebra” refers to this free tree algebra, not to the anticommutative algebras bearing the same name in another part of algebra.

Choose two distinct named elements 0,1∈TG0,1 \in T_G. If GG has two chosen generators they may be used; if G={g}G = \{g\}, the elements gg and g∗gg * g may be used. The names need not denote leaves. Although GG may be infinite or uncountable, we do not put a constant symbol for every generator into the signature. All computational signatures below remain finite. Define total projections by

L(u∗v)=u,R(u∗v)=v,L(g)=R(g)=g(g∈G).L(u * v) = u, \qquad R(u * v) = v, \qquad L(g) = R(g) = g \quad(g \in G).

We use the notation

M=(TG;∗,0,1),M+=(TG;∗,L,R,0,1),\mathcal{M} = (T_G; *, 0, 1), \qquad\mathcal{M}^{+} = (T_G; *, L, R, 0, 1),

and, for any unary predicate V⊆TGV \subseteq T_G,

MV=(TG;∗,V,0,1),MV+=(TG;∗,L,R,V,0,1).\mathcal{M}_V = (T_G; *, V, 0, 1), \qquad\mathcal{M}^{+}_V = (T_G; *, L, R, V, 0, 1).

Thus ∗* is a pairing function and L,RL, R are its left and right projections. These names will be used consistently throughout the paper.

The second running example is standard arithmetic

N=(N;+,⋅,0,1),N={0,1,2,…}.\mathcal{N} = (\mathbb{N}; +, \cdot, 0, 1), \qquad\mathbb{N} = \{0, 1, 2, \ldots\}.

For V⊆NV \subseteq\mathbb{N}, put NV=(N;+,⋅,0,1,V)\mathcal{N}_V = (\mathbb{N}; +, \cdot, 0, 1, V). The pairing and projections used in the argument are definable functions of this structure, rather than assumed primitives of its original signature. Cantor’s pairing function is

c(x,y)=(x+y)(x+y+1)2+y.c(x,y) = \frac{(x+y)(x+y+1)}{2} + y.

For each n∈Nn \in\mathbb{N}, let ss be the unique nonnegative integer with

s(s+1)2≤n<(s+1)(s+2)2,\frac{s(s+1)}{2} \leq n < \frac{(s+1)(s+2)}{2},

put r=n−s(s+1)/2r = n - s(s+1)/2, and define Lc(n)=s−rL_c(n) = s-r and Rc(n)=rR_c(n) = r. The interval has s+1s+1 integers, so 0≤r≤s0 \leq r \leq s. Consequently

Lc(c(x,y))=x,Rc(c(x,y))=y,c(Lc(n),Rc(n))=n.L_c(c(x,y)) = x, \qquad R_c(c(x,y)) = y, \qquad c(L_c(n),R_c(n)) = n.

Indeed, c(x,y)c(x,y) belongs to the displayed interval with s=x+ys=x+y and r=yr=y; conversely, the formula reconstructs every nn. This proves that c:N2→Nc : \mathbb{N}^{2} \to\mathbb{N} is a bijection and that its two coordinate maps are total.

For definability in the original arithmetic signature, use the quantifier-free graph formula

Γc(x,y,z)⟺z+z=(x+y)⋅(x+y+1)+(y+y).(1)\Gamma_c(x,y,z) \Longleftrightarrow z+z = (x+y)\cdot(x+y+1) + (y+y). \tag*{(1)}

In N\mathcal{N}, this is equivalent to z=c(x,y)z=c(x,y). The projection graphs are defined by the existential arithmetic formulas

ΓLc(n,x)⟺∃y Γc(x,y,n),ΓRc(n,y)⟺∃x Γc(x,y,n).\Gamma_{L_c}(n,x) \Longleftrightarrow\exists y\,\Gamma_c(x,y,n), \qquad\Gamma_{R_c}(n,y) \Longleftrightarrow\exists x\,\Gamma_c(x,y,n).

Bijectivity proves that these formulas define total single-valued functions. No division or order symbol occurs in the graph definitions. These same definitions remain valid in every expansion by additional predicates or functions.

When the argument calls for these functions as primitive instructions, we use only the auxiliary definitional expansion

Npair=(N;+,⋅,c,Lc,Rc,0,1),NVpair=(Npair,V).\mathcal{N}^{\mathrm{pair}} = (\mathbb{N}; +, \cdot, c, L_c, R_c, 0, 1), \qquad\mathcal{N}^{\mathrm{pair}}_V = (\mathcal{N}^{\mathrm{pair}}, V).

First-order definability alone does not supply a deterministic unit-cost algorithm for producing a function’s value. The graph of cc has a bounded-time test, and the projection graphs belong to NP in every arithmetic expansion. Under a hypothetical P=NP\mathrm{P} = \mathrm{NP}, Lemma 4.1 permits adjoining these functions while preserving the collapse. Corollary 4.3 then transfers the pairing obstruction to the original arithmetic signature. The running example remains N\mathcal{N}. § 4.2.2 considers an elementary arithmetic signature in which cc, LcL_c, RcR_c are fixed term functions.

Machines, input length, and complexity classes

Let L\mathcal{L} be a fixed finite signature of total functions, relations, and constants, and let S\mathcal{S} be an L\mathcal{L}-structure with universe SS. Equality is always available as a test. We assume that two distinct elements, denoted by 0,10,1, are named or obtainable by fixed ground terms. Replacing such ground terms by named constants changes running time by at most a fixed initialization cost.

A machine over SS has a finite program, finitely many states, and finitely many tapes. A data cell contains one element of SS. The elementary instructions are copying a cell, writing a named constant, moving a tape head by one position, applying one primitive function, testing equality or a primitive relation, and testing whether a cell is blank. Each instruction costs one time unit. A fixed finite control alphabet and a blank marker are permitted; they do not supply additional elements of SS. This is the multitape formulation used in [22 Section 2].

An input is a tuple xˉ∈Sn\bar{x} \in S^n, and its size is ∣xˉ∣=n|\bar{x}| = n. In particular, neither the height of a tree nor the bit length of an external representation of a structure element contributes to input length. A primitive function call costs one step, but evaluating a variable-length term requires executing its individual operation occurrences. Finite descriptions of formulas and programs will be given as explicit binary words, whose lengths are charged in full. Here a binary description means a word over the two-letter alphabet {0,1}\{0,1\} encoding the syntax, instruction names, and indices; it is not an external representation of the structure elements on which the program operates.

Definition 2.2. The class DTIME⁡S(t(n))\operatorname{DTIME}_{S}(t(n)) consists of the languages X⊆S∗=⋃n≥0SnX \subseteq S^* = \bigcup_{n\ge0} S^n decided by deterministic machines over SS in time O(t(n))O(t(n)) on every length-nn input. Define

P(S)=⋃k≥1DTIME⁡S((n+2)k),EXP(S)=⋃k≥1DTIME⁡S(2(n+2)k).\mathrm{P}(S)=\bigcup_{k\ge1}\operatorname{DTIME}_{S}((n+2)^k), \qquad\mathrm{EXP}(S)=\bigcup_{k\ge1}\operatorname{DTIME}_{S}(2^{(n+2)^k}).

Nondeterministic machines may guess arbitrary elements of SS. The analogous polynomial-time class is NP(S)\mathrm{NP}(S). Equivalently, X∈NP(S)X \in\mathrm{NP}(S) if there are a deterministic polynomial-time verifier DD and a polynomial qq such that

xˉ∈X⟺∃yˉ∈Sq(∣xˉ∣) D(xˉ,yˉ)=1.\bar{x} \in X \quad\Longleftrightarrow\quad\exists\bar{y}\in S^{q(|\bar{x}|)}\ D(\bar{x},\bar{y})=1.

The two tuples are supplied with their lengths, or on separate input tapes; either convention is polynomially equivalent to a self-delimiting concatenation.

All time bounds are uniform in the values of the input elements. Padding witnesses by a named constant allows one to replace “length at most q(n)q(n)” by “length exactly q(n)q(n)”. Binary branching can be simulated by guessing a value and verifying that it is 00 or 11. A witness for NP need not be a binary word: its entries can be arbitrary elements of SS. We distinguish this from binary nondeterminism in the next subsection.

At first, a program may use only the constants of the fixed signature. This is the convention of [22]. The versions allowing a finite tuple of additional constants in each program are denoted by Ppar(S)\mathrm{P}_{\mathrm{par}}(S) and NPpar(S)\mathrm{NP}_{\mathrm{par}}(S) and are discussed in Section 2.6. Both the positive and the negative conclusions of this paper hold under either convention.

Binary nondeterminism and polynomial hierarchies

The bounded-quantifier description of the polynomial hierarchy is classical [24]; alternation gives its corresponding machine interpretation [4]. Full and binary, also called digital, polynomial hierarchies over arbitrary structures are studied in [3]. We specify the quantifier domains because unrestricted structure-element guesses and binary guesses have different roles in the trace argument. The mixed-domain notation below is introduced explicitly for this paper.

Definition 2.3 (Binary nondeterminism). The class NBP⁡(S)\operatorname{NBP}(S) consists of languages X⊆S∗X \subseteq S^* for which there are a deterministic polynomial-time verifier DD over SS and a polynomial qq such that, with n=∣xˉ∣n = |\bar{x}|,

xˉ∈X⟺∃εˉ∈{0,1}q(n) D(xˉ,εˉ)=1.\bar{x} \in X \quad\Longleftrightarrow\quad\exists\bar{\varepsilon} \in\{0,1\}^{q(n)}\ D(\bar{x},\bar{\varepsilon}) = 1.

Thus the witness, but not necessarily the input, is a binary word. Write coNBP⁡(S)\operatorname{coNBP}(S) for the complements of these languages, with complement taken in S∗S^*. We have

P(S)⊆NBP⁡(S)⊆NP⁡(S).P(S) \subseteq\operatorname{NBP}(S) \subseteq\operatorname{NP}(S).

The second inclusion follows by verifying that every guessed entry is either 0 or 1.

Definition 2.4 (Full and mixed polynomial hierarchies). Set Σ0P(S)=Π0P(S)=P(S)\Sigma_0^P(S) = \Pi_0^P(S) = P(S). For a fixed k≥1k \ge1, a language X⊆S∗X \subseteq S^* belongs to ΣkP(S)\Sigma_k^P(S) if there are polynomial bounds p1,…,pkp_1,\ldots,p_k and a deterministic polynomial-time predicate DD such that, for n=∣xˉ∣n = |\bar{x}|,

xˉ∈X⟺∃yˉ1∈Sp1(n) ∀yˉ2∈Sp2(n) ⋯ Qkyˉk∈Spk(n) D(xˉ,yˉ1,…,yˉk)=1,\bar{x} \in X \quad\Longleftrightarrow\quad\exists\bar{y}_1 \in S^{p_1(n)}\ \forall\bar{y}_2 \in S^{p_2(n)}\ \cdots\ Q_k\bar{y}_k \in S^{p_k(n)}\ D(\bar{x},\bar{y}_1,\ldots,\bar{y}_k) = 1,

where the blocks alternate and QkQ_k is existential for odd kk and universal for even kk. The class ΠkP(S)\Pi_k^P(S) is defined by starting with a universal block, or equivalently by complementation. In particular,

Σ1P(S)=NP⁡(S),Π1P(S)=coNP⁡(S).\Sigma_1^P(S) = \operatorname{NP}(S), \qquad\Pi_1^P(S) = \operatorname{coNP}(S).

The full polynomial hierarchy is

PH⁡(S)=⋃k≥0(ΣkP(S)∪ΠkP(S)).\operatorname{PH}(S) = \bigcup_{k\ge0}\left(\Sigma_k^P(S) \cup\Pi_k^P(S)\right).

All tuple boundaries are explicit, all bounds concern numbers of cells, and the running time of DD is polynomial in the total input length. Polynomial witness bounds are taken to have nonnegative integer values at every input length.

For a mixed hierarchy, let B={0,1}B = \{0,1\} and choose a domain τi∈{S,B}\tau_i \in\{S,B\} for each block. Replacing Spi(n)S^{p_i(n)} above by τipi(n)\tau_i^{p_i(n)} defines our notation Σkτ1,…,τk(S)\Sigma_k^{\tau_1,\ldots,\tau_k}(S), and starting universally defines Πkτ1,…,τk(S)\Pi_k^{\tau_1,\ldots,\tau_k}(S). Thus the all-SS classes are the full classes, Σ1B(S)=NBP⁡(S)\Sigma_1^B(S) = \operatorname{NBP}(S), and the all-BB classes use only binary quantifier blocks. In particular, a language XX belongs to Σ2S,B(S)\Sigma_2^{S,B}(S) if and only if there are fixed polynomials p,qp,q and a deterministic polynomial-time predicate DD such that, for every input xˉ\bar{x} of length nn,

xˉ∈X⟺∃yˉ∈Sp(n) ∀εˉ∈Bq(n) D(xˉ,yˉ,εˉ)=1.(2)\bar{x} \in X \quad\Longleftrightarrow\quad\exists\bar{y} \in S^{p(n)}\ \forall\bar{\varepsilon} \in B^{q(n)}\ D(\bar{x},\bar{y},\bar{\varepsilon}) = 1. \tag*{(2)}

Every mixed class at level kk is contained in the corresponding full class. For an existential binary block, quantify over SS and require that every entry be 0 or 1; for a universal binary block, use that same condition as the antecedent of an implication. These guards have polynomial-time tests and add no quantifier alternation. In particular,

Σ2S,B(S)⊆Σ2P(S)⊆PH⁡(S).\Sigma_2^{S,B}(S) \subseteq\Sigma_2^P(S) \subseteq\operatorname{PH}(S).

The matrices in these definitions are polynomial-time predicates; we are not requiring one fixed quantifier-free formula to express every variable-length computation of such a matrix.

Proposition 2.5 (Collapse of the full and mixed hierarchies). If P(S)=NP⁡(S)P(S) = \operatorname{NP}(S), then

PH⁡(S)=P(S).\operatorname{PH}(S) = P(S).

Every fixed level of every mixed hierarchy also equals P(S)P(S). In particular, Σ2S,B(S)=P(S)\Sigma_2^{S,B}(S) = P(S).

Proof. Eliminate the quantifier blocks from the inside out. An existential block of polynomially many structure elements applied to a polynomial-time predicate defines an NP(S)NP(S) relation, and hence, under the hypothesis, a P(S)P(S) relation. For a universal block, complement the predicate, eliminate the resulting existential block, and complement the answer. Deterministic polynomial time is closed under complementation. Previously quantified tuples remain part of the input, with their boundaries and the original input length retained, so every witness bound stays polynomial in the current input length. This proves by induction that every fixed full level is contained in P(S)P(S). The reverse inclusions use predicates that ignore their quantified variables. The mixed classes are contained in the corresponding full classes, and the same argument with unused variables proves equality for them. The number of blocks is fixed for each language; no uniform polynomial bound for unbounded alternation is asserted.

The problem SAT(SS)

Definition 2.6. An instance of SAT⁡(S)\operatorname{SAT}(S) consists of an explicit binary encoding wψw_\psi of an existential L\mathcal{L}-formula

ψ(xˉ)=∃yˉ θ(xˉ,yˉ),\psi(\bar{x}) = \exists\bar{y}\ \theta(\bar{x},\bar{y}),

where θ\theta is quantifier-free, together with a tuple aˉ∈S∣xˉ∣\bar{a} \in S^{|\bar{x}|}. The instance is accepted exactly when S⊨ψ(aˉ)S \models\psi(\bar{a}). Its length is ∣wψ∣+∣aˉ∣|w_\psi| + |\bar{a}|, up to a fixed choice of delimiters. Malformed encodings or incorrect parameter arities are rejected. The matrix may contain arbitrary Boolean combinations and negative occurrences of every relation symbol, including VV when it is present.

Proposition 2.7 (Structure-relative satisfiability). The problem SAT⁡(S)\operatorname{SAT}(S) is NP(S)NP(S)-complete under polynomial-time many-one reductions over SS. Consequently,

P(S)=NP(S)⟺SAT⁡(S)∈P(S).P(S) = NP(S) \qquad\Longleftrightarrow\qquad\operatorname{SAT}(S) \in P(S).

Proof. For membership, guess the values of the quantified variables and evaluate the explicit quantifier-free matrix. Variable names and the syntax tree can be processed with polynomial overhead; each operation or relation occurrence requires one primitive call after its arguments have been evaluated.

For hardness, fix a nondeterministic polynomial-time machine and a polynomial clock T(n)≥nT(n) \ge n bounding every branch. During T(n)T(n) steps, every tape uses at most O(T(n))O(T(n)) relevant cells. Describe a computation tableau with one row for each time and one column for each relevant tape cell. Introduce variables for the data values, blank flags, head positions, states, and nondeterministic choices. There are polynomially many variables and local conditions. Finite control values are represented by fixed tuples of binary variables, each constrained by b=0∨b=1b = 0 \lor b = 1. A function instruction is imposed by an equation z=f(u1,…,ur)z = f(u_1,\ldots,u_r). A relation test with a binary result bb is imposed by

(b=1∧R(uˉ))∨(b=0∧¬R(uˉ)).(b = 1 \land R(\bar{u})) \lor(b = 0 \land\neg R(\bar{u})).

Copying, unchanged tape cells, tape movements, and conditional instructions have fixed-size local descriptions. Require the initial row to contain the given input tuple as its free parameters and the final row to be accepting, after making accepting states absorbing. Existentially quantify all internal data and control variables. The resulting formula is satisfiable precisely when the original machine has an accepting branch.

The syntax of this formula is produced in polynomial time, independently of the values of the input parameters. Every intermediate value has its own variable, so shared computation is not expanded into an exponentially long term. This is the Cook construction [5] over the primitive operations of SS; see [22 Theorems 2–3] for its structure-relative formulation.

Remark 2.8. The witness variables in this proof need not be binary. In particular, the proposition is about arbitrary-element nondeterminism. We also make no general assertion that NP⁡(S)⊆EXP⁡(S)\operatorname{NP}(S) \subseteq\operatorname{EXP}(S): over an arbitrary infinite structure there need not be an effective bounded enumeration of all possible witness values.

The deterministic separation P differs from EXP

The following argument is the padded universal-machine diagonalization underlying the deterministic time hierarchy of Hartmanis and Stearns [10]. We supply the proof over SS, because its primitive operations and relations may have no effective presentation as ordinary Turing-computable functions or predicates.

Lemma 2.9 (Universal simulation). For a fixed finite signature there is a universal machine over SS which, given a binary program description ee, an input xˉ\bar{x}, and a bound tt on the number of simulated steps, simulates those steps in time

(∣e∣+∣xˉ∣+t+2)O(1).(|e| + |\bar{x}| + t + 2)^{O(1)}.

The exponent is independent of ee, xˉ\bar{x}, and tt.

Proof. Use a finite binary instruction format specifying states, tape indices, and one of the finitely many operation or relation symbols. The universal machine stores the simulated tapes, their head markers, and the current state. In tt steps the number of represented tape positions is bounded by a polynomial in ∣e∣+∣xˉ∣+t|e| + |\bar{x}| + t. A full scan of this representation locates the current cells of the tapes addressed by an instruction. A scan of the finite description finds the instruction and its possible successor states.

The number of arguments of a primitive is bounded by the maximum arity in the fixed signature. The universal machine copies those arguments into its working cells and applies that same primitive operation or test. Dispatch among the finitely many primitive names is part of its finite program. Updating the tape representation and its markers requires at most another polynomial number of moves. This deliberately inefficient implementation has polynomial total overhead, with a fixed exponent. It interprets primitive names, not external representations of their values; no ordinary algorithm for a primitive’s interpretation is required.

Theorem 2.10 (Deterministic separation). For every finite-signature structure with two distinct available elements,

P⁡(S)⊊EXP⁡(S).\operatorname{P}(S) \subsetneq\operatorname{EXP}(S).

In particular, the conclusion applies to the free Malcev algebra, standard arithmetic N\mathcal{N}, and all their finite expansions, including the structures with primitive pairing and projections used in § 3.

Proof. Choose an effective binary coding of finite programs. A padded description has the form

w=1∣e∣0e0r,r≥0,w = 1^{|e|}0e0^{r}, \qquad r \ge0,

where ee is a valid program code. Thus every fixed program has descriptions of arbitrarily large length. On a nonbinary or malformed input, the diagonal machine rejects. On a valid ww of length nn, it simulates the program described by ee on the entire input ww for at most 2n2^n simulated steps. If the simulated program accepts within the bound, it rejects; if that program rejects within the bound, it accepts; on timeout it rejects.

An (n+1)(n+1)-bit clock counts the simulated steps. Lemma 2.9, together with the polynomial overhead for the clock, gives total running time 2O(n)2^{O(n)} times a polynomial factor. The diagonal language HH therefore belongs to EXP⁡(S)\operatorname{EXP}(S). Suppose that a machine DD decides HH in polynomial time. Let eDe_D be its fixed program code and choose rr so large that the running time of DD on length n=2∣eD∣+1+rn=2\lvert e_D\rvert+1+r is less than 2n2^n. On w=1∣eD∣0eD0rw=1^{\lvert e_D\rvert}0e_D0^r, the diagonal machine then observes DD halt and gives the opposite answer. This contradicts the assumption that DD decides HH. Hence H∉P(S)H\notin\mathrm{P}(S). The non-strict inclusion follows directly from the definitions.

Finitely many program constants

Lemma 2.11. If P(S)=NP(S)\mathrm{P}(S)=\mathrm{NP}(S), then the same equality holds after naming any finite tuple cˉ∈Sm\bar{c}\in S^m. Moreover,

Ppar(S)=NPpar(S)⟺for some finite cˉ, P(S,cˉ)=NP(S,cˉ).\mathrm{P}_{\mathrm{par}}(S)=\mathrm{NP}_{\mathrm{par}}(S)\quad\Longleftrightarrow\quad\text{for some finite }\bar{c},\ \mathrm{P}(S,\bar{c})=\mathrm{NP}(S,\bar{c}).

Proof. For the first assertion, use Proposition 2.7. In an existential formula of the expanded language replace each new constant symbol by a fresh free variable and supply its actual value as an additional parameter cell. This is polynomial syntactic preprocessing, and the given solver for SAT⁡(S)\operatorname{SAT}(S) decides the resulting instance. The number of added parameter cells is fixed.

If the parameter-allowing classes collapse, the base-language problem SAT⁡(S)\operatorname{SAT}(S) has a deterministic polynomial-time solver using some finite tuple cˉ\bar{c} of program constants. Name that tuple. The same substitution reduces SAT⁡(S,cˉ)\operatorname{SAT}(S,\bar{c}) to the base-language problem, giving a fixed-signature collapse. Conversely, suppose a finite expansion by cˉ\bar{c} has a collapse. A given parameter-allowing nondeterministic machine uses some further finite tuple dˉ\bar{d}. The first assertion gives a collapse after naming both tuples, and therefore a deterministic polynomial-time decider with finitely many program constants. This is the finite-constant reduction discussed in [22 p. 461].

Thus any obstruction proved for every finite constant expansion also excludes the parameter-allowing collapse. Any positive fixed-signature example gives a positive example under the parameter-allowing convention as well.

Pairing, computation traces, and the problem Bad(AA)

Throughout this section SS is a finite-signature structure containing distinct available elements 00, 11, a binary operation ∗\ast, and total unary operations LL, RR satisfying

L(u∗v)=u,R(u∗v)=v(u,v∈S).(3)L(u\ast v)=u,\qquad R(u\ast v)=v\qquad(u,v\in S). \tag*{(3)}

We call ∗\ast a pairing function and LL, RR its projections. These identities imply that ∗\ast is jointly injective. No other identity, in particular no identity L(z)∗R(z)=zL(z)\ast R(z)=z for arbitrary zz, is assumed. Additional finitely many operations and relations are allowed. They will be used in the transition checks exactly as they are interpreted in SS.

The free Malcev algebra with its projections and the auxiliary definitional expansion Npair\mathcal{N}^{\mathrm{pair}} of standard arithmetic satisfy (3). In the latter, ∗\ast is interpreted as cc, and LL, RR as LcL_c, RcR_c. It is not a free tree algebra: c(0,0)=0c(0,0)=0 and Lc(0)=Rc(0)=0L_c(0)=R_c(0)=0, so repeated projections may cycle. The argument uses only (3), totality, and equality; it requires neither freeness nor well-foundedness of arbitrary elements. In this section the projections are primitive instructions. We do not infer the same cost bounds for their evaluation in the original {+,⋅,0,1}\{+,\cdot,0,1\}-reduct from definability alone; the transfer to that reduct is proved in Corollary 4.3. The unconditional simulation by terms in elementary arithmetic is given in § 4.2.2.

Arrays represented by one element

For b1⋯bd∈{0,1}db_1 \cdots b_d \in\{0,1\}^d, with the most significant bit first, put

Addr⁡d(T;b1⋯bd)=Pbd(⋯Pb2(Pb1(T))⋯ ),P0=L,P1=R.\operatorname{Addr}_d(T;b_1\cdots b_d)=P_{b_d}(\cdots P_{b_2}(P_{b_1}(T))\cdots), \qquad P_0=L,\quad P_1=R.

For 0≤i<2d0 \le i < 2^d, we also write Addr⁡d(T;i)\operatorname{Addr}_d(T;i), using the length-dd binary expansion of ii, including leading zeroes. The integer notation refers to ordinary binary control; it introduces no arithmetic operation on SS.

Lemma 3.1 (Packing and access). Given any list C0,…,C2d−1C_0,\ldots,C_{2^d-1} of elements of SS, there is an element T∈ST \in S such that Addr⁡d(T;i)=Ci\operatorname{Addr}_d(T;i)=C_i for every ii. An entry can be accessed in O(d)O(d) steps when the address is supplied in dd binary cells. Conversely, every T∈ST \in S determines such a list of extracted values, without any shape assumption on TT.

Proof. For d=0d=0 take T=C0T=C_0. Inductively pack the first and second halves of the list into T0,T1T_0,T_1 and set T=T0∗T1T=T_0*T_1. The first address bit selects the correct half by (3), and the induction hypothesis handles the remaining bits. The access algorithm reads one bit and applies its indicated projection at each step. Finally, LL and RR are total, so every sequence of dd projection calls has a value on every TT.

The existence part of the lemma does not give a polynomial-time construction of an arbitrary exponential array. The trace algorithm below guesses its root as one arbitrary structure element. This distinction is essential.

Canonical configurations and transitions

Fix a deterministic machine AA over the full signature of SS. Here AA denotes a program; the calligraphic letter A\mathcal{A} in Section 5 will denote the unary structure. Encode every auxiliary finite control symbol by a fixed-size block over {0,1}\{0,1\}, using extra tapes if needed. Since AA is fixed, this normalization has constant overhead and lets us assume that every nonblank tape cell contains an element of SS. We describe a configuration encoding for which one transition has a bounded-time test, independently of the sizes of the encoded tapes.

For a fixed number mm of fields, use the tuple code

pack⁡m(z1,…,zm)=z1∗(z2∗(⋯∗(zm∗0)⋯ )).\operatorname{pack}_m(z_1,\ldots,z_m)=z_1*(z_2*(\cdots*(z_m*0)\cdots)).

Its fields are recovered by fixed projection terms, and the tuple map is injective. Encode the finitely many states by distinct fixed-length binary tuples, packed in this way. Distinctness follows from (3), without any freeness assumption.

Use tagged stacks, writing push⁡(a,s)\operatorname{push}(a,s) for the result of placing the element aa at the top of the stack ss:

nil⁡=0∗0,push⁡(a,s)=1∗(a∗s).(4)\operatorname{nil}=0*0,\qquad\operatorname{push}(a,s)=1*(a*s). \tag*{(4)}

For a nonempty valid stack ss, its top and remaining stack are

head⁡(s)=L(R(s)),tail⁡(s)=R(R(s)).\operatorname{head}(s)=L(R(s)),\qquad\operatorname{tail}(s)=R(R(s)).

The equality nil⁡=push⁡(a,s)\operatorname{nil}=\operatorname{push}(a,s) is impossible because their left projections are 00 and 11. This works even if the distinguished elements themselves belong to the image of ∗*. In particular, it works in Npair\mathcal{N}^{\mathrm{pair}}, where every natural number belongs to the image of Cantor pairing. Finite stacks remain unambiguously decodable because the empty and nonempty tags are distinct; no global condition on the shapes of arbitrary elements is used.

Separately tag tape cells by

blank⁡=0∗0,data⁡(a)=1∗a.\operatorname{blank}=0*0,\qquad\operatorname{data}(a)=1*a.

A blank is distinct from every tagged data cell, including a cell whose data value is 0, 1, or one of the encoding tags. A tape is represented by three fields (ℓ,c,r)(\ell,c,r): the stack to the left of the head, the current tagged cell, and the stack to its right. In either stack the nearest cell comes first. An empty stack represents an unvisited blank half-tape.

Popping an empty stack returns (blank,nil)(\mathrm{blank},\mathrm{nil}); popping a nonempty valid stack returns its head and tail. For an arbitrary s≠nils \ne\mathrm{nil}, use the same projection formulas to define pop⁡(s)\operatorname{pop}(s). This fixes a total convention on malformed stacks without asserting their validity. A move to the right replaces (ℓ,c,r)(\ell,c,r) by

(push⁡(c,ℓ),c′,r′),(c′,r′)=pop⁡(r).(\operatorname{push}(c,\ell),c',r'), \qquad(c',r')=\operatorname{pop}(r).

A move to the left is symmetric. A data write changes only the current cell, and primitive tests are applied to the decoded current data values. Operations on blank operands may be normalized to a fixed rejecting transition, after an explicit blank test. This only fixes the semantics on cases where a data instruction has no operand and does not restrict the computations under consideration.

A valid configuration is the canonical packed tuple of a state and the tape fields of AA, with finite tagged stacks as just described. A represented tape may retain extra blank cells that have been visited; its encoding is part of the configuration. The successor update is fixed by the stack rules, so there is a unique encoded successor even when two different encodings would describe the same extensional infinite blank tape.

Lemma 3.2 (Exact local transition test). For the fixed machine AA there are constant-time tests Step⁡A(C,C′)\operatorname{Step}_{A}(C,C') and Acc⁡A(C)\operatorname{Acc}_{A}(C) with the following properties:

  1. if CC is valid, exactly one C′C' satisfies Step⁡A(C,C′)\operatorname{Step}_{A}(C,C'), namely the canonical encoded successor of CC;

  2. that successor is valid;

  3. on valid configurations, Acc⁡A\operatorname{Acc}_{A} is precisely the accepting-state test.

The initial configuration Init⁡A(xˉ)\operatorname{Init}_{A}(\bar{x}) is constructible in O(∣xˉ∣+1)O(|\bar{x}|+1) steps. The accepting and rejecting halting states can be made absorbing.

Proof. The number of fields in a configuration depends only on AA. Extract them by the fixed projection terms. If the decoded state is not one of the machine’s state codes, the transition test returns false. Otherwise, perform the instruction’s actual primitive operation or relation test. The formulas for stack movement, copying, and writing determine all updated fields using a bounded number of primitive calls.

For each instruction and branch, require C′C' to equal the whole canonical tuple obtained by packing those updated fields. This equality is a single structure equality test after a bounded number of constructions. Taking the finite disjunction of the instruction cases defines Step⁡A\operatorname{Step}_{A}. On a valid CC, determinism chooses exactly one case; the stack formulas preserve validity and give its unique encoded successor. Testing the decoded state gives Acc⁡A\operatorname{Acc}_{A}. Self-loops at halting states are implemented by C′=CC'=C on those states.

To initialize the input tape, tag the input elements and build its right stack from right to left. Its left stack is empty, and the remaining tapes are blank with empty stacks. This requires a linear number of pairing calls. The other fields take constant time.

No global validity test on arbitrary stacks is needed. The assertions concern successors of valid configurations, and validity will propagate from the known initial configuration. The whole-target equality is nevertheless indispensable: checking only the projections of C′C' could admit noncanonical elements, since (3) does not imply L(z)∗R(z)=zL(z)*R(z)=z for every zz.

Errors in an exponentially long trace

For d≥1d \ge1, a proposed initial configuration I∈SI \in S, and a proposed trace T∈ST \in S, put

Ci=Addr⁡d(T;i)(0≤i<2d).C_i = \operatorname{Addr}_d(T;i) \qquad(0 \le i < 2^d).

Define the language Bad⁡(A)\operatorname{Bad}(A) on inputs (1d,I,T)(1^d,I,T) by

(1d,I,T)∈Bad⁡(A)⟺C0≠I∨¬Acc⁡A(C2d−1)(1^d,I,T) \in\operatorname{Bad}(A) \quad\Longleftrightarrow\quad C_0 \ne I \mathbin{\vee} \neg\operatorname{Acc}_A(C_{2^d-1})
∨∃i<2d−1 ¬Step⁡A(Ci,Ci+1).(5)\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\mathbin{\vee} \exists i < 2^d-1\ \neg\operatorname{Step}_A(C_i,C_{i+1}). \tag*{(5)}

The last two input cells contain I,TI,T, and the preceding cells form the unary word 1d1^d. Inputs outside this format are, by convention, in Bad⁡(A)\operatorname{Bad}(A). Thus its input length is exactly d+2d+2 on well-formed instances, independently of the represented size of II and TT. The machine AA is fixed, not part of this input.

Lemma 3.3 (Finding an error). For each fixed AA,

Bad⁡(A)∈NBP⁡(S)⊆NP⁡(S).\operatorname{Bad}(A) \in\operatorname{NBP}(S) \subseteq\operatorname{NP}(S).

Its verifier uses only polynomially many binary choices and has a polynomial running-time bound in d+2d+2, uniform in I,TI,T. Consequently the no-error language is in coNBP⁡(S)\operatorname{coNBP}(S).

Proof. First check the input format in linear time and accept immediately if it fails. Otherwise choose one of the three error types in (5) using a fixed number of binary branches. For the initial error, apply LL exactly dd times to TT, compare the result with II, and accept if they differ. For the final error, apply RR exactly dd times and accept if Acc⁡A\operatorname{Acc}_A fails. These branches take O(d+1)O(d+1) primitive steps apart from ordinary tape management.

For a transition error, guess a word b1⋯bdb_1\cdots b_d and verify that each entry is 0 or 1. Reject the branch if all entries are 1, since that word denotes the last position and has no successor in the array. Compute the binary successor word by carrying from the last bit; this uses O(d)O(d) bit operations and requires no arithmetic on SS. Copy TT into two working cells and follow the two address words to obtain CiC_i and Ci+1C_{i+1}. Apply the constant-time test of Lemma 3.2 and accept precisely when it fails.

Every branch has a polynomial bound in d+2d+2. If an endpoint is wrong, its corresponding branch accepts. If a transition is wrong, the branch guessing its index accepts. Conversely, an accepting branch certifies one of the displayed errors. This proves exact membership in Bad⁡(A)\operatorname{Bad}(A).

Define the accepted-trace language on well-formed inputs by

Trace⁡(A)={(1d,I):d≥1, ∃T∈S (1d,I,T)∉Bad⁡(A)},\operatorname{Trace}(A)=\{(1^d,I):d\ge1,\ \exists T\in S\ (1^d,I,T)\notin\operatorname{Bad}(A)\},

and reject inputs outside this format. Its input length is d+1d+1. Here II is any element of SS: validity of II is not included as an extra membership test. The following lemma gives the interpretation when II is a valid configuration.

Lemma 3.4 (Exact traces and the mixed second level). For each fixed AA,

Trace⁡(A)∈Σ2S,B(S)⊆Σ2P(S).\operatorname{Trace}(A) \in\Sigma^{S,B}_2(S) \subseteq\Sigma^P_2(S).

More precisely, there is a deterministic polynomial-time predicate QAQ_A such that

(1d,I)∈Trace⁡(A)⟺∃T∈S ∀eˉ∈{0,1}d QA(1d,I,T,eˉ).(6)(1^d,I)\in\operatorname{Trace}(A)\quad\Longleftrightarrow\quad\exists T\in S\ \forall\bar{e}\in\{0,1\}^d\ Q_A(1^d,I,T,\bar{e}). \tag*{(6)}

If II is a valid configuration of AA, then for every d≥1d\ge1,

∃T∈S ((1d,I,T)∉Bad⁡(A))⟺A accepts from I within 2d−1 transitions.(7)\exists T\in S\ ((1^d,I,T)\notin\operatorname{Bad}(A))\quad\Longleftrightarrow\quad A\text{ accepts from }I\text{ within }2^d-1\text{ transitions.} \tag*{(7)}

Proof. For a well-formed input and a binary address εˉ∈{0,1}d\bar{\varepsilon} \in\{0,1\}^{d}, let QAQ_A assert

Addr⁡d(T;0d)=I,Acc⁡A(Addr⁡d(T;1d)),\operatorname{Addr}_d(T;0^d)=I,\qquad\operatorname{Acc}_A(\operatorname{Addr}_d(T;1^d)),
εˉ=1dorStep⁡A(Addr⁡d(T;εˉ),Addr⁡d(T;εˉ+1)).\bar{\varepsilon}=1^d\quad\text{or}\quad\operatorname{Step}_A(\operatorname{Addr}_d(T;\bar{\varepsilon}),\operatorname{Addr}_d(T;\bar{\varepsilon}+1)).

The last test is performed only when εˉ≠1d\bar{\varepsilon}\ne1^d; εˉ+1\bar{\varepsilon}+1 denotes the binary successor word computed by the carry procedure in Lemma 3.3. The endpoints and the two addressed configurations are accessed using O(d)O(d) projection calls, and Lemma 3.2 supplies the local tests. Thus QAQ_A is decidable in polynomial time in d+2d+2, uniformly in I,TI,T. Its matrix rejects malformed inputs. To use quantifier lengths defined for every input length nn, give the universal word length nn and, on a well-formed input n=d+1n=d+1, ignore its last bit.

Every possible transition position is represented by a binary address, while the all-one address requires only the endpoint checks. Therefore the universal assertion is equivalent to the absence of all three errors in (5). This proves (6) and the mixed-class membership. The existential block contains just one arbitrary structure element. We now establish the claimed acceptance equivalence for valid II.

Suppose first that TT has no error. Its first extracted entry is C0=IC_0=I, hence is valid. We prove by induction on ii that CiC_i is the actual canonical configuration reached after ii transitions. The assertion holds at i=0i=0. If it holds at i<2d−1i<2^d-1, the absence of a transition error gives Step⁡A(Ci,Ci+1)\operatorname{Step}_A(C_i,C_{i+1}). Lemma 3.2 makes Ci+1C_{i+1} the unique actual successor and makes it valid. This proves the induction. The last entry satisfies Acc⁡A\operatorname{Acc}_A, so the machine accepts within the stated bound.

Conversely, suppose that AA accepts after h≤2d−1h\le2^d-1 transitions. List its actual configurations through time hh, and repeat the accepting configuration until the list has exactly 2d2^d entries. These repetitions are legal because the accepting state is absorbing. Lemma 3.1 supplies a root TT whose extracted entries are exactly this list. Its initial entry is II, its final entry is accepting, and all adjacent pairs pass the transition test. None of the alternatives in (5) holds.

The forward argument applies to every candidate TT, including elements that do not have a recognizable full-tree shape. Only the extracted entries and their exact successor relation are used.

The obstruction

Proposition 3.5 (Exponential time in the mixed second level). For every structure satisfying the assumptions of this section,

EXP⁡(S)⊆Σ2S,B(S)⊆Σ2P(S).\operatorname{EXP}(S)\subseteq\Sigma^{S,B}_2(S)\subseteq\Sigma^P_2(S).

In the first inclusion a single arbitrary structure element suffices for the existential block.

Proof. Let X∈EXP⁡(S)X\in\operatorname{EXP}(S) be decided by a fixed deterministic machine AA in time at most 2q(n)2^{q(n)}, after increasing the polynomial qq to absorb constants and small input lengths. Set

d=q(n)+1,I=Init⁡A(xˉ).d=q(n)+1,\qquad I=\operatorname{Init}_A(\bar{x}).

The map xˉ↦(1d,I)\bar{x}\mapsto(1^d,I) is computable in polynomial time and has polynomial output length. The initial configuration is valid, and

2q(n)≤2q(n)+1−1=2d−1.2^{q(n)}\le2^{q(n)+1}-1=2^d-1.

As both accepting and rejecting halting states are absorbing, Lemma 3.4 gives

xˉ∈X⟺∃T∈S ∀εˉ∈{0,1}q(n)+1 QA(1q(n)+1,Init⁡A(xˉ),T,εˉ).\bar{x}\in X\quad\Longleftrightarrow\quad\exists T\in S\ \forall\bar{\varepsilon}\in\{0,1\}^{q(n)+1}\ Q_A(1^{q(n)+1},\operatorname{Init}_A(\bar{x}),T,\bar{\varepsilon}).

Its deterministic matrix first performs the polynomial-time preprocessing and then the test QAQ_A. This is the required mixed second-level definition, without any collapse assumption.

Theorem 3.6 (Pairing obstruction). Every finite-signature structure SS satisfying (3), with equality and two distinct available elements, satisfies

P(S)≠NP(S).P(S) \ne NP(S).

The conclusion remains valid after any finite expansion by additional total functions, relations, or constants, and under the convention allowing finitely many arbitrary program constants.

Proof. Assume P(S)=NP(S)P(S) = NP(S). Proposition 2.5 and Proposition 3.5 give

EXP⁡(S)⊆Σ2S,B(S)⊆PH⁡(S)=P(S),\operatorname{EXP}(S) \subseteq\Sigma^{S,B}_{2}(S) \subseteq\operatorname{PH}(S) = P(S),

contrary to Theorem 2.10. To spell out the two nondeterministic steps underlying this hierarchy argument, let X∈EXP⁡(S)X \in\operatorname{EXP}(S) and fix a deterministic decider AA for XX whose running time on length-nn inputs is at most 2q(n)2^{q(n)}, for an integer-valued polynomial qq. Increasing qq absorbs constant factors and the finitely many small input lengths.

By Lemma 3.3, the assumed equality gives a deterministic polynomial-time decider for Bad⁡(A)\operatorname{Bad}(A). Complementing its output gives such a decider for the absence of errors. On input xˉ∈Sn\bar{x} \in S^{n}, perform the following nondeterministic computation: construct

I=Init⁡A(xˉ),d=q(n)+1,I = \operatorname{Init}_{A}(\bar{x}), \qquad d = q(n) + 1,

write 1d1^{d}, guess one arbitrary element T∈ST \in S, and use the deterministic decider to check that (1d,I,T)∉Bad⁡(A)(1^{d}, I, T) \notin\operatorname{Bad}(A). All deterministic work is polynomial in nn, since the tested instance has length d+2d + 2.

By Lemma 3.4, this procedure accepts exactly when AA accepts xˉ\bar{x} within 2d−12^{d} - 1 transitions. Since

2q(n)≤2q(n)+1−1,2^{q(n)} \leq2^{q(n)+1} - 1,

and rejecting states are absorbing, this is exactly the language XX. Therefore X∈NP(S)=P(S)X \in NP(S) = P(S). As XX was arbitrary, EXP⁡(S)⊆P(S)\operatorname{EXP}(S) \subseteq P(S), contradicting Theorem 2.10.

Any finite expansion still has a finite signature and the identities (3); its actual additional primitives can be included in both the universal simulation and the transition test. The same proof therefore applies to it. Finally, a parameter-allowing collapse would yield a collapse in some finite constant expansion by Lemma 2.11, which has just been excluded.

Corollary 3.7 (No fast existential truth predicate). No finite expansion of a structure satisfying (3) admits a uniform polynomial-time algorithm for SAT in its full signature. In particular, no unary predicate VV in such an expansion can satisfy

V(Cψ(aˉ))⟺ψ(aˉ)V(C_{\psi}(\bar{a})) \Longleftrightarrow\psi(\bar{a})

for every existential formula of the expanded language and every parameter tuple, when Cψ(aˉ)C_{\psi}(\bar{a}) is uniformly constructible in polynomial unit cost from the explicit formula and the tuple.

Proof. Such an algorithm, or such a code construction followed by one VV-test, puts SAT in PP. Proposition 2.7 would give P=NPP = NP, contrary to Theorem 3.6.

Remark 3.8 (Role of the hypotheses). The proof uses a binary address to locate an error, but its outer witness is an arbitrary structure element containing the complete trace. It does not prove a separation between deterministic and binary-nondeterministic polynomial time. It also uses unit-cost equality of arbitrary elements, notably of complete configuration codes. The theorem concerns this specified computation model, not a model in which the cost of comparing or guessing a tree is its expanded size. In the auxiliary expansion Npair\mathcal{N}^{\mathrm{pair}} the trace witness is one natural number, even when its usual binary representation is very long. The trace inclusion of Proposition 3.5 applies to that expansion; its unconditional transfer to the original {+,⋅,0,1}\{+, \cdot, 0, 1\}-reduct is not asserted. Corollary 4.7 gives an unconditional transfer in the elementary arithmetic signature. The result is about unit-cost computation over the displayed structure and does not settle the classical finite-alphabet P versus NP question.

Arithmetic, Malcev’s algebra, and the absence of projections

Simulating operations by their graphs

We next remove L,RL, R from the hypotheses on the original language. We use decision-class simulations; no passage from a decidable graph to a deterministic witness-producing function is assumed.

Lemma 4.1 (Simulation by graphs). Assume P(S)=NP(S)\mathrm{P}(S) = \mathrm{NP}(S). Let S+S^{+} be obtained by adjoining finitely many total functions whose graphs belong to NP(S)\mathrm{NP}(S). Then, as decision classes on the same universe,

NP(S+)=P(S+)=P(S).\mathrm{NP}(S^{+}) = \mathrm{P}(S^{+}) = \mathrm{P}(S).

Proof. Under the assumed collapse, every added graph has a deterministic polynomial-time decider over SS. Simulate a nondeterministic polynomial-time S+S^{+}-machine over SS. For every call to an added function, guess its proposed output and check the graph. A failed check rejects that simulation branch. Totality ensures that a correct guess exists; single-valuedness ensures that every successful guess is the intended output. All later tests, including negative relation tests, are therefore performed on the correct data. Only polynomially many calls and checks occur. Thus

NP(S+)⊆NP(S)=P(S)⊆P(S+)⊆NP(S+).\mathrm{NP}(S^{+}) \subseteq\mathrm{NP}(S) = \mathrm{P}(S) \subseteq\mathrm{P}(S^{+}) \subseteq\mathrm{NP}(S^{+}).

These inclusions prove the assertion. □\square

Theorem 4.2 (Injective binary operations). Let SS be a finite-signature structure with two distinct available elements and a jointly injective binary primitive ∗:S2→S\ast: S^{2} \to S. Then

P(S)≠NP(S).\mathrm{P}(S) \ne\mathrm{NP}(S).

This holds under either constant convention and in every finite expansion retaining ∗\ast.

Proof. Suppose that the classes collapse. The image relation

Node⁡(t)⟺∃u,v  (t=u∗v)\operatorname{Node}(t) \Longleftrightarrow\exists u,v\;(t = u \ast v)

belongs to NP(S)\mathrm{NP}(S) and hence to P(S)\mathrm{P}(S); its complement has a polynomial-time decider as well. Define total projections by taking the unique components on the image of ∗\ast and returning tt off that image. Their graphs are

ΓL(t,u)⟺(∃v  t=u∗v)∨(¬Node⁡(t)∧u=t),\Gamma_{L}(t,u) \Longleftrightarrow(\exists v\;t = u \ast v) \lor(\neg\operatorname{Node}(t) \land u = t),
ΓR(t,v)⟺(∃u  t=u∗v)∨(¬Node⁡(t)∧v=t).\Gamma_{R}(t,v) \Longleftrightarrow(\exists u\;t = u \ast v) \lor(\neg\operatorname{Node}(t) \land v = t).

Both graphs are in NP(S)\mathrm{NP}(S): choose the relevant alternative, guess its component when needed, or use the deterministic complement-of-image test. Injectivity makes the selected components unique.

By Lemma 4.1, adjoining L,RL, R preserves the assumed collapse. Their definitions give L(u∗v)=uL(u \ast v) = u and R(u∗v)=vR(u \ast v) = v, contradicting Theorem 3.6. The argument applies in every finite expansion. Lemma 2.11 then gives the parameter-allowing conclusion. □\square

Arithmetic and truth predicates

Standard arithmetic

Corollary 4.3 (Standard arithmetic and its finite expansions). Every finite expansion SS of N=(N;+,⋅,0,1)\mathcal{N}=(\mathbb{N};+,\cdot,0,1) satisfies P(S)≠NP(S)\mathrm{P}(S)\ne\mathrm{NP}(S), under either convention for program constants. In particular, for every V⊆NV\subseteq\mathbb{N},

P(NV)≠NP(NV).\mathrm{P}(\mathcal{N}_V)\ne\mathrm{NP}(\mathcal{N}_V).

Consequently, no such VV admits a uniformly polynomial-time code construction Cψ(aˉ)C_\psi(\bar{a}) over NV\mathcal{N}_V satisfying

Cψ(aˉ)∈V⟺NV⊨ψ(aˉ)(8)C_\psi(\bar{a})\in V \quad\Longleftrightarrow\quad\mathcal{N}_V\models\psi(\bar{a}) \tag*{(8)}

for all existential formulas of the expanded language {+,⋅,0,1,V}\{+,\cdot,0,1,V\} and all parameter tuples. The matrix may contain negative occurrences of VV, and the input to the encoder consists of the explicit formula and the tuple.

Proof. Suppose that a finite expansion SS of N\mathcal{N} has a collapse. Formula (1) and the two projection formulas define the graphs of cc, LcL_c, RcR_c by existential formulas in the original arithmetic language. Their graphs therefore lie in NP(S)\mathrm{NP}(S). By Lemma 4.1, adjoining these three total functions preserves the assumed equality. The resulting structure satisfies (3), contradicting Theorem 3.6. This argument works for every finite expansion, so Lemma 2.11 also excludes a collapse with arbitrary finitely many program constants. Equivalently, the conclusion is an instance of the first-order definable pairing obstruction stated in Corollary 4.11 below.

Finally, a polynomial-time encoder satisfying (8), followed by one VV-test, would decide SAT(NV)\mathrm{SAT}(\mathcal{N}_V) in polynomial time. Proposition 2.7 would imply the excluded collapse. No arithmetical definability or ordinary computability assumption on VV is used; the encoder itself may use VV as a primitive test.

There is also a direct term version of the arithmetic argument:

j(x,y)=(x+y)⋅(x+y+1)+(y+y)=2c(x,y)j(x,y)=(x+y)\cdot(x+y+1)+(y+y)=2c(x,y)

is jointly injective and is computed by a fixed arithmetic term. Adjoining jj changes neither polynomial-time class, since every call is replaced by a bounded number of arithmetic instructions; Theorem 4.2 therefore gives the same contradiction. The pairing-only structures (N;c,0,1)(\mathbb{N};c,0,1) and (N;c,Lc,Rc,0,1)(\mathbb{N};c,L_c,R_c,0,1) also satisfy the separation by the earlier theorems, but the corollary above concerns the original arithmetic signature and all its finite expansions.

For conventional effective syntax coding, the claim about existential truth also has a direct diagonal form with no efficiency hypothesis. This statement is separate from the more flexible coding condition (8). We first distinguish a formula, its numerical code, and a numeral denoting that code.

Definition 4.4 (Syntax codes, numerals, and diagonal substitution). Let L\mathcal{L} be one of the arithmetic languages considered here, including the unary relation symbol VV, and fix an injective Gödel coding of its finite syntactic expressions by natural numbers. For an expression α\alpha, the notation ⌜α⌝\ulcorner\alpha\urcorner denotes its numerical code. For n∈Nn\in\mathbb{N}, fix the closed numeral

0‾=0,n+1‾=(n‾+1).\underline{0}=0,\qquad\underline{n+1}=(\underline{n}+1).

Thus n‾\underline{n} is a term, whereas nn is a number, and the value of n‾\underline{n} in every arithmetic expansion considered here is nn. The notation ⌜α⌝\ulcorner\alpha\urcorner is used in the metalanguage; its code is named inside a formula by the corresponding numeral.

Fix a distinguished variable xx. A formula is admissible for the following substitution operation if its free variables are contained in {x}\{x\}. If q=⌜α⌝q=\ulcorner\alpha\urcorner is the code of such a formula, define

Sub⁡L(q,n)=⌜α[n/x]⌝.\operatorname{Sub}_{\mathcal L}(q,n)=\ulcorner\alpha[n/x]\urcorner.

Here α[n/x]\alpha[n/x] is obtained by replacing every free occurrence of xx by the numeral nn; bound occurrences are unchanged. The numeral is closed, so this substitution cannot cause variable capture, and the resulting formula is a sentence.

If qq is not the code of an admissible formula, we define Sub⁡L(q,n)=0\operatorname{Sub}_{\mathcal L}(q,n)=0 for every nn. This default output is a number, not a truth value; it only makes the numerical function defined on all inputs. Define the diagonal-substitution function by

dL(q)=Sub⁡L(q,q).d_{\mathcal L}(q)=\operatorname{Sub}_{\mathcal L}(q,q).

In particular, if q=⌜α(x)⌝q=\ulcorner\alpha(x)\urcorner is admissible, then

dL(q)=⌜α[q/x]⌝.d_{\mathcal L}(q)=\ulcorner\alpha[q/x]\urcorner.

These operations manipulate finite syntax only. They never use the interpretation of VV.

For an effective coding, expressions can be encoded and decoded algorithmically, well-formedness and free-variable tests are decidable, and numeral substitution is computable. The above convention then makes Sub⁡L\operatorname{Sub}_{\mathcal L} and dLd_{\mathcal L} total computable numerical functions. We will use a stronger, elementary version of these requirements in § 4.2.2.

Proposition 4.5 (No existential truth predicate for its own arithmetic language). Fix an effective Gödel coding of Lar(V)={+,⋅,0,1,V}\mathcal L_{\rm ar}(V)=\{+,\cdot,0,1,V\} with the recognition and substitution properties just specified. There is no V⊆NV\subseteq\mathbb{N} such that

⌜σ⌝∈V⟺NV⊨σ(9)\ulcorner\sigma\urcorner\in V\quad\Longleftrightarrow\quad\mathcal N_V\models\sigma \tag*{(9)}

for every existential sentence σ\sigma of this same expanded language, allowing negative VV-atoms in its quantifier-free matrix.

Proof. Write Sub⁡ar\operatorname{Sub}_{\rm ar} and dard_{\rm ar} for the functions of Definition 4.4 in this language. The admissible formulas here may have arbitrary quantifiers; only their free variables are restricted. On input qq, an ordinary algorithm checks admissibility, constructs the numeral qq, and substitutes it for the free occurrences of xx, returning 00 in the inadmissible case. Thus dard_{\rm ar} is total computable, regardless of the interpretation of VV.

Its graph is a computably enumerable subset of N2\mathbb{N}^{2}. By the Davis–Putnam–Robinson–Matiyasevich theorem [15], there is a quantifier-free formula δ(x,z,uˉ)\delta(x,z,\bar{u}) in the original arithmetic language {+,⋅,0,1}\{+,\cdot,0,1\} such that, for all a,z∈Na,z\in\mathbb{N},

N⊨∃uˉ δ(a,z,uˉ)⟺z=dar(a).(10)\mathcal N\models\exists\bar{u}\,\delta(a,z,\bar{u})\quad\Longleftrightarrow\quad z=d_{\rm ar}(a). \tag*{(10)}

Here a,za,z on the left specify the values assigned to the two free variables. For each aa, witnesses uˉ\bar{u} exist when z=dar(a)z=d_{\rm ar}(a) and do not exist for any other zz. The output zz is unique; the auxiliary witnesses uˉ\bar{u} need not be unique.

Choose the displayed variables distinct and form the formula

β(x)=∃z∃uˉ (δ(x,z,uˉ)∧¬V(z)).\beta(x)=\exists z\exists\bar{u}\,(\delta(x,z,\bar{u})\land\neg V(z)).

It has no free variable other than xx and is existential in Lar(V)\mathcal L_{\rm ar}(V). Since δ\delta contains no VV, its interpretation is the same in N\mathcal N and NV\mathcal N_V.

Equation (10) therefore gives, for every a∈Na \in\mathbb{N},

NV⊨β[a/x]⟺∃z∈N (z=dar(a) and z∉V)\mathcal{N}_V \models\beta[a/x] \Longleftrightarrow\exists z \in\mathbb{N}\ (z=d_{\mathrm{ar}}(a)\ \text{and}\ z \notin V)
⟺dar(a)∉V.\Longleftrightarrow d_{\mathrm{ar}}(a) \notin V.

Now take the numerical code of this already constructed formula and then perform the indicated substitution:

e=⌜β(x)⌝,λ=β[e/x].e=\ulcorner\beta(x)\urcorner,\qquad\lambda=\beta[e/x].

The formula λ\lambda is a closed existential sentence. By the definition of diagonal substitution,

dar(e)=Sub⁡ar(e,e)=⌜β[e/x]⌝=⌜λ⌝.d_{\mathrm{ar}}(e)=\operatorname{Sub}_{\mathrm{ar}}(e,e)=\ulcorner\beta[e/x]\urcorner=\ulcorner\lambda\urcorner.

Thus ee codes the one-variable formula, while dar(e)d_{\mathrm{ar}}(e) codes the sentence obtained by substituting the numeral for that formula’s code. Specializing the preceding semantic equivalence to a=ea=e yields

NV⊨λ⟺⌜λ⌝∉V.\mathcal{N}_V \models\lambda\Longleftrightarrow\ulcorner\lambda\urcorner\notin V.

If (9) held, applying it to this particular existential sentence would give

⌜λ⌝∈V⟺NV⊨λ⟺⌜λ⌝∉V,\ulcorner\lambda\urcorner\in V \Longleftrightarrow\mathcal{N}_V \models\lambda\Longleftrightarrow\ulcorner\lambda\urcorner\notin V,

a contradiction. There is no circular definition: the numerical function dard_{\mathrm{ar}} and its arithmetic graph representation are fixed first, then β\beta, then its code ee, and finally λ\lambda. Diophantine representation is what keeps λ\lambda in the purely existential fragment.

Remark 4.6 (Comparison with Tarski and other truth predicates). Tarski’s undefinability theorem excludes an arithmetic formula defining the full truth set of the original arithmetic language [26]; the distinction between object language and metalanguage is also explained in [25 Sections 7–10]. It does not prevent the external set of true arithmetic sentences from being named by a new predicate. Restricted truth predicates are possible as well: the true existential sentences of the original language form a computably enumerable set, hence an existentially definable set by the same Diophantine representation theorem [15]. Such predicates describe truth for the original language; they do not satisfy (9) for the language containing the predicate itself. Negating an arithmetic definition of existential truth need not preserve existential form, whereas ¬V(z)\neg V(z) is quantifier-free in the expanded language.

Proposition 4.5 is a Tarski-style diagonal obstruction for standard effective codes, with no complexity bound. Corollary 4.3 instead excludes every uniformly fast code construction in the unit-cost model, even one using an arbitrary primitive VV and therefore not necessarily computable in the ordinary sense. The main pairing proof requires neither Diophantine representation nor an arithmetization of syntactic self-reference. Kripke’s fixed-point truth predicates allow truth-value gaps [13]; they do not provide the total classical predicate required by the displayed biconditionals. The positive unary construction in Section 5 uses a different structure and coding scheme; this arithmetic diagonal argument does not by itself apply to it.

Elementary arithmetic and term representations

Let Elem denote the class of Kalmár elementary functions: the smallest class containing the constants, coordinate projections, addition, and truncated subtraction, and closed under substitution, bounded summation, and bounded product. Mazzanti’s substitution-basis results represent these functions by fixed arithmetic terms [16]. We use the three-operation basis of Prunescu, Sauras-Altuzarra and Shunia [23 Theorem 1]:

Elem⁡=⟨x+y, x mod y, 2x⟩sub.(11)\operatorname{Elem}=\langle x+y,\ x\bmod y,\ 2^x\rangle_{\mathrm{sub}}. \tag*{(11)}

Here the brackets mean closure under substitution, with constants and coordinate projections available. Define

Nel=(N;+,mod⁡,exp⁡2,0,1),exp⁡2(x)=2x,\mathcal{N}_{\mathrm{el}} = (\mathbb{N}; +, \operatorname{mod}, \exp_2, 0, 1), \qquad\exp_2(x) = 2^x,

using the total convention xmod⁡0=xx \operatorname{mod} 0 = x. Every constant needed by a fixed term can be built from 00, 11 and addition, so the basis theorem does not require an infinite computational signature.

Cantor pairing cc and its two projections are elementary. For the projections, the inverse description in § 2.1 can be written as

s(n)=∑k=1n1{k(k+1)≤2n},r(n)=n−s(n)(s(n)+1)2,s(n) = \sum_{k=1}^{n} \mathbf{1}_{\{k(k+1)\le2n\}}, \qquad r(n) = n - \frac{s(n)(s(n)+1)}{2},
Lc(n)=s(n)−r(n),Rc(n)=r(n).L_c(n) = s(n) - r(n), \qquad R_c(n) = r(n).

The symbol 11 denotes the characteristic function of the indicated elementary relation. The bounded sum and the remaining functions are elementary; all displayed subtractions are nonnegative. Equation (11) therefore supplies fixed terms tc(x,y),tL(z),tR(z)t_c(x,y), t_L(z), t_R(z) in the language of Nel\mathcal{N}_{\mathrm{el}} representing cc, LcL_c, RcR_c. In particular,

tL(tc(x,y))=x,tR(tc(x,y))=y.t_L(t_c(x,y)) = x, \qquad t_R(t_c(x,y)) = y.

Each term has a fixed finite number of operation occurrences. Its unit-cost evaluation is uniformly bounded, independently of the values of its arguments. No uniform bound on the sizes of terms representing all elementary functions is needed.

This conclusion depends on the signature. Every unary term in {+,⋅,0,1}\{+,\cdot,0,1\} is a polynomial with nonnegative integer coefficients and is therefore nondecreasing. But

Lc(1)=1>Lc(2)=0,Rc(2)=1>Rc(3)=0.L_c(1) = 1 > L_c(2) = 0, \qquad R_c(2) = 1 > R_c(3) = 0.

Thus the projections are not terms in that original language. Their ordinary computability and first-order definability are compatible with this fact.

Corollary 4.7 (Elementary arithmetic and its finite expansions). For every finite expansion SS of Nel\mathcal{N}_{\mathrm{el}},

P(S)⊊EXP(S)⊆Σ2S,B(S)⊆PH(S),\mathrm{P}(S) \subsetneq\mathrm{EXP}(S) \subseteq\Sigma^{S,B}_2(S) \subseteq\mathrm{PH}(S),
P(S)≠NP(S).\mathrm{P}(S) \ne\mathrm{NP}(S).

In particular, P(S)⊊Σ2S,B(S)\mathrm{P}(S) \subsetneq\Sigma^{S,B}_2(S). These statements hold for arbitrary interpretations of the additional primitives, including an arbitrary unary predicate VV. Either convention for finitely many program constants gives the same classes here.

Proof. Adjoin cc, LcL_c, RcR_c as primitive functions. Replace each call to an added function by evaluation of its fixed defining term. This incurs only constant overhead and preserves P, NP, EXP, and all fixed levels of the full and mixed polynomial hierarchies. For the hierarchies, the quantified domains and polynomial bounds are unchanged, and the deterministic matrix computation is simulated by the same replacement. These simulations require no collapse hypothesis and remain valid with every additional primitive interpreted as in SS.

The expanded structure satisfies (3). Apply Proposition 3.5 and Theorem 3.6, and transfer their conclusions back by this simulation. The strict inclusion P⊊EXP\mathrm{P} \subsetneq\mathrm{EXP} is Theorem 2.10. Finally, every extra program constant is a natural number and can be initialized by a fixed numeral, so allowing finitely many such constants does not change the classes.

The same argument applies in any finite-signature structure with two available distinct elements whenever pairing and its projections are represented by fixed terms satisfying (3); uniformly bounded-time implementations suffice as well. Multiplication itself is a term function of Nel\mathcal{N}_{\mathrm{el}} by (11), so its separation also follows from Corollary 4.3 after adjoining multiplication. The additional conclusion here is the unconditional simulation of the projections and the resulting trace inclusion in the original Nel\mathcal{N}_{\mathrm{el}} signature.

The elementary basis also sharpens the syntactic diagonal argument. We use the distinction between codes and numerals from Definition 4.4, now for the language

Lel(V)={+,mod⁡,exp⁡2,0,1,V}.\mathcal{L}_{\mathrm{el}}(V)=\{+,\operatorname{mod},\operatorname{exp}_{2},0,1,V\}.

The required syntax operations will be elementary numerical functions, rather than merely computable ones.

Here is one concrete way to obtain such a coding. Choose a finite alphabet for expressions, including digits for variable indices, and represent its symbols by digits ai∈{0,…,B−1}a_i \in\{0,\ldots,B-1\} for a fixed base B≥2B \ge2 large enough for the alphabet. Encode a string a0⋯am−1a_0\cdots a_{m-1} by

enc⁡(a0⋯am−1)=Bm+∑i=0m−1aiBm−1−i.\operatorname{enc}(a_0\cdots a_{m-1})=B^m+\sum_{i=0}^{m-1}a_iB^{m-1-i}.

The initial base-BB digit 1 records the length, including any leading zero digits of the string. Fully parenthesized expressions and explicit variable indices give decidable syntax and free-variable tests. Use the unary numerals of Definition 4.4. If a formula has code qq, its length is O(log⁡(q+2))O(\log(q+2)), whereas the numeral nn has O(n+1)O(n+1) symbols. Replacing the free occurrences of xx therefore produces O((n+1)log⁡(q+2))O((n+1)\log(q+2)) symbols, with numerical code at most

BO((n+1)log⁡(q+2)).B^{O((n+1)\log(q+2))}.

Parsing, checking variable occurrences, and constructing the substituted string can be carried out by ordinary algorithms whose running time is bounded by a fixed polynomial in q+n+2q+n+2. This is a deliberately loose bound, since the input string has only O(log⁡(q+2))O(\log(q+2)) symbols. Their numerical outputs have elementary bounds as well. Hence the syntax tests, numeral construction, and totalized substitution functions in this coding are elementary. The following proposition applies to any coding with these properties.

Proposition 4.8 (No quantifier-free truth predicate in elementary arithmetic). Put Nel,V=(Nel,V)\mathcal{N}_{\mathrm{el},V}=(\mathcal{N}_{\mathrm{el}},V) and fix a Gödel coding of $\mathcal{L}_{\mathrm{el}}(V) for which the recognition of quantifier-free formulas whose free variables are contained in {x}\{x\}, and substitution of the numerals nn, are elementary. Denote this restricted substitution function by Sub⁡qf(q,n)\operatorname{Sub}_{\mathrm{qf}}(q,n), with the meaning given in Definition 4.4 on admissible formulas.

If qq does not code a quantifier-free formula with free variables contained in {x}\{x\}, define Sub⁡qf(q,n)=0\operatorname{Sub}_{\mathrm{qf}}(q,n)=0 for every nn. This default value only makes the numerical function defined on every input; it does not assign a truth value to an invalid expression.

There is no V⊆NV\subseteq\mathbb{N} such that

σ−∈V  ⟺  Nel,V⊨σ(12)\sigma^{-}\in V \iff\mathcal{N}_{\mathrm{el},V}\models\sigma \tag*{(12)}

for every quantifier-free sentence σ\sigma of this same expanded language, allowing negative VV-atoms. No definability or ordinary computability assumption is made on VV.

Proof. First define the total numerical function

dqf(q)=Sub⁡qf(q,q).d_{\mathrm{qf}}(q)=\operatorname{Sub}_{\mathrm{qf}}(q,q).

It is elementary by the hypothesis on substitution and closure under composition. In particular, if q=⌜α(x)⌝q = \ulcorner\alpha(x)\urcorner is admissible, then

dqf(q)=⌜α[q/x]⌝.d_{\mathrm{qf}}(q)=\ulcorner\alpha[q/x]\urcorner.

This function depends only on the chosen coding and on finite syntax; it never tests membership in VV.

By (11), choose a fixed term td(x)t_d(x) using only ++, mod⁡\operatorname{mod}, exp⁡2\operatorname{exp}_2, 00, 11 such that

tdNel(a)=dqf(a)(a∈N).(13)t_d^{\mathcal{N}_{\mathrm{el}}}(a)=d_{\mathrm{qf}}(a) \qquad(a\in\mathbb{N}). \tag*{(13)}

The left-hand side means the numerical value of this term when xx is assigned aa. The term is fixed before the next formula is formed and contains no occurrence of VV.

Form the quantifier-free formula

β(x)=¬V(td(x)).\beta(x)=\neg V(t_d(x)).

When taking its code, write out the entire arithmetic term td(x)t_d(x): the notation tdt_d is an abbreviation in the proof, not a new function symbol in the coded language. Only after this expansion set

e=⌜β(x)⌝,λ=β[e/x]=¬V(td(e)).e=\ulcorner\beta(x)\urcorner,\qquad\lambda=\beta[e/x]=\neg V(t_d(e)).

Because the numeral ee is closed and β\beta has no other free variables, λ\lambda is a quantifier-free sentence of the same language. Its code is

dqf(e)=Sub⁡qf(e,e)=⌜λ⌝.d_{\mathrm{qf}}(e)=\operatorname{Sub}_{\mathrm{qf}}(e,e)=\ulcorner\lambda\urcorner.

The numeral ee denotes the number ee, so (13) gives the following value for the closed term occurring inside λ\lambda:

(td(e))Nel=tdNel(e)=dqf(e)=⌜λ⌝.\bigl(t_d(e)\bigr)^{\mathcal{N}_{\mathrm{el}}}=t_d^{\mathcal{N}_{\mathrm{el}}}(e)=d_{\mathrm{qf}}(e)=\ulcorner\lambda\urcorner.

Thus the semantics of the single negative VV-atom in λ\lambda gives

Nel,V⊨λ⟺⌜λ⌝∉V.\mathcal{N}_{\mathrm{el},V}\models\lambda\quad\Longleftrightarrow\quad\ulcorner\lambda\urcorner\notin V.

Applying the proposed truth condition (12) to λ\lambda would instead require

⌜λ⌝∈V⟺Nel,V⊨λ⟺⌜λ⌝∉V,\ulcorner\lambda\urcorner\in V\quad\Longleftrightarrow\quad\mathcal{N}_{\mathrm{el},V}\models\lambda\quad\Longleftrightarrow\quad\ulcorner\lambda\urcorner\notin V,

a contradiction. The construction uses the substitution function first, its representing term second, and only then the formula and its code. The term representation replaces the existential graph witnesses used in Proposition 4.5, so the diagonal sentence here remains quantifier-free.

Proposition 4.8 concerns the specified syntax coding. It does not exclude arbitrary VV-dependent encoders of quantifier-free truth: if fixed numbers a∈Va\in V and b∉Vb\notin V are available, such an encoder can evaluate a quantifier-free input formula using VV and return aa or bb according to its truth value. Corollary 4.7, together with Proposition 2.7, still excludes a uniformly polynomial-time encoder of existential truth in the full expanded language. The new diagonal proposition strengthens the fragment in Proposition 4.5 by changing the arithmetic signature and imposing the elementary coding hypothesis; the comparison with external and partial truth predicates in Remark 4.6 continues to apply.

The negative answer to the final Les petits cailloux question

Recall the free Malcev algebra of Definition 2.1, for an arbitrary nonempty generator set GG. Its universe TGT_G is defined recursively: every g∈Gg \in G is a tree, and for u,v∈TGu,v \in T_G the expression u∗vu * v is a tree. Generators are distinct from all products, and two products are equal if and only if their respective left and right subtrees are equal. Every element is a finite term. This is the Malcev algebra considered here; it is not the anticommutative algebraic structure also called a Malcev algebra in other contexts.

Choose two distinct named elements 0,1∈TG0,1 \in T_G and write

M=(TG;∗,0,1),MV=(TG;∗,V,0,1).\mathcal{M}=(T_G; *,0,1), \qquad\mathcal{M}_V=(T_G; *,V,0,1).

When GG contains two designated generators they may be used as 0,10,1. For a one-generator algebra, one may instead use that generator and its product with itself. The proof does not require the named elements to be leaves. Define total projections by

L(u∗v)=u,R(u∗v)=v,L(g)=R(g)=g(g∈G),L(u*v)=u, \qquad R(u*v)=v, \qquad L(g)=R(g)=g \quad(g\in G),

and put MV+=(TG;∗,L,R,V,0,1)\mathcal{M}_V^+=(T_G; *,L,R,V,0,1).

Corollary 4.9 (Negative answer to Question 1.1). For every unary predicate V⊆TGV \subseteq T_G,

P(MV)≠NP(MV),P(MV+)≠NP(MV+).P(\mathcal{M}_V)\ne NP(\mathcal{M}_V), \qquad P(\mathcal{M}_V^+)\ne NP(\mathcal{M}_V^+).

Consequently there is no truth-predicate expansion of Malcev’s algebra answering Poizat’s free-tree question positively, in the unit-cost framework of Les petits cailloux. The statement holds for every cardinality of GG, in every finite further expansion, and under either constant convention.

Proof. The pairing function of TGT_G is jointly injective, so Theorem 4.2 applies to MV\mathcal{M}_V. The expanded structure MV+\mathcal{M}_V^+ satisfies (3), so Theorem 3.6 applies to it directly. Both results permit arbitrary additional primitives in a fixed finite signature, including the chosen interpretation of VV. The final assertions are part of those theorems.

Corollary 4.10 (The two projection conventions). For every V⊆TGV \subseteq T_G,

[P(MV)=NP(MV)]⟺[P(MV+)=NP(MV+)].[P(\mathcal{M}_V)=NP(\mathcal{M}_V)] \Longleftrightarrow[P(\mathcal{M}_V^+)=NP(\mathcal{M}_V^+)].

Both statements are false. The implication from a collapse in the pairing language to a collapse in the projection language is already supplied by a computation simulation.

Proof. Under a hypothetical collapse for MV\mathcal{M}_V, the complement of Node⁡(t)\operatorname{Node}(t) is decidable in polynomial time. In the free algebra it is exactly the set of generators. Thus the two graphs in the proof of Theorem 4.2 are the graphs of the specified projections fixing generators, and Lemma 4.1 gives a collapse for MV+\mathcal{M}_V^+. Corollary 4.9 rules out the latter and also rules out the former. This proves the displayed equivalence with both sides false.

The equivalence is not an assertion that adding projections preserves the individual deterministic complexity classes without hypotheses. The simulation guesses projection outputs and uses the hypothetical collapse; it does not compute those outputs deterministically merely because their graphs are decidable.

Corollary 4.11 (First-order definable pairing). If a finite-signature structure with two distinct available elements satisfies P=NPP=NP, there is no total jointly injective map J:S2→SJ:S^2 \to S whose graph is first-order definable, even with finitely many parameters.

Proof. First name the finitely many definition parameters, preserving the collapse by Lemma 2.11. By Proposition 2.5, every fixed first-order definable relation is polynomial-time decidable under a collapse. Explicitly, induct on the fixed formula, using closure under Boolean combinations and the fact that existential projection of a polynomial-time relation is in NP=P\mathrm{NP} = \mathrm{P}. Universal quantification follows by complementation. This is an induction for each fixed formula, not a uniform bound for arbitrary quantifier alternation.

The graph of JJ is consequently in P\mathrm{P} and hence in NP\mathrm{NP}. Lemma 4.1 allows us to adjoin JJ while retaining the collapse. Theorem 4.2 gives a contradiction. The parameter-allowing version follows by first applying Lemma 2.11 to a finite expansion with a fixed-signature collapse.

Infinite structures with binary operations and P=NP\mathrm{P} = \mathrm{NP}

We now recall the unary existence theorem and derive five structures with binary operations. In this section the letters A,…,F\mathcal{A},\ldots,\mathcal{F} refer to these particular examples. Each asserted class equality concerns the entire displayed signature.

Theorem 5.1 (Prunescu [21 Theorem 5.2]). There is a countably infinite structure

A=(U;s0,s1,p,a,V)\mathcal{A} = (U; s_0, s_1, p, a, V)

with three unary functions, one constant, and one unary predicate, such that SAT⁡(A)\operatorname{SAT}(\mathcal{A}) is decidable in polynomial unit cost and

P(A)=NP(A).\mathrm{P}(\mathcal{A}) = \mathrm{NP}(\mathcal{A}).

Its universe is a countably infinite disjoint union of rooted successor trees: on each component s0s_0 and s1s_1 freely generate the finite words from the root, p(si(u))=up(s_i(u)) = u, and pp fixes the root. The constant aa names one root. In particular, s0,s1s_0, s_1 are injective with disjoint images, pp is surjective, and all the values s0j(a)s_0^j(a), j≥0j \ge0, are distinct.

The theorem gives a quadratic bound in its explicit formula encoding. Renaming the finitely many occurring variables to consecutive indices converts the explicit finite-alphabet encodings used here to that encoding with only polynomial overhead. Only the polynomial bound and the displayed algebraic properties will be used here; the construction of VV is not repeated. The distinct ground-term values s0(a)s_0(a) and s1(a)s_1(a) can serve as the binary values. Naming finitely many fixed ground-term values does not change any of the complexity classes.

Lemma 5.2 (Replacing primitive instructions). Let two finite-signature structures have the same universe. If every primitive operation and relation of either structure is computable by a fixed bounded-time program over the other, and the named constants can also be initialized in bounded time, their deterministic and nondeterministic polynomial-time classes coincide.

Proof. Replace each primitive instruction by its fixed simulation. The running time changes by at most a constant factor and a fixed initialization cost. An arbitrary guessed element is the same witness in either structure, so the same replacement also applies to nondeterministic computations.

A binary operation retaining the unary predicate

Set

c0=a,c1=s0(a),c2=s1(a),c_0 = a,\qquad c_1 = s_0(a),\qquad c_2 = s_1(a),

and define on UU

x⋆y={s0(y),x=c0,s1(y),x=c1,p(y),x=c2,x,x∉{c0,c1,c2}.x \star y = \begin{cases} s_0(y), & x=c_0,\\ s_1(y), & x=c_1,\\ p(y), & x=c_2,\\ x, & x\notin\{c_0,c_1,c_2\}. \end{cases}

Let B=(U;⋆,V,a)\mathcal{B}=(U;\star,V,a).

Corollary 5.3. The countably infinite structure B\mathcal{B} has one binary operation, one unary predicate, and one constant, and satisfies P(B)=NP(B)\mathrm{P}(\mathcal{B})=\mathrm{NP}(\mathcal{B}). Its binary operation depends essentially on both arguments, and the subalgebra generated by aa is infinite.

Proof. The tags and the unary functions of A\mathcal{A} are recovered by

c1=a⋆a,c2=(a⋆a)⋆a,c_1=a\star a,\qquad c_2=(a\star a)\star a,
s0(y)=a⋆y,s1(y)=c1⋆y,p(y)=c2⋆y.s_0(y)=a\star y,\qquad s_1(y)=c_1\star y,\qquad p(y)=c_2\star y.

The predicate and the constant are unchanged. Conversely, the displayed case definition computes ⋆\star over A\mathcal{A} using finitely many equality tests and one old operation. Thus Lemma 5.2 and Theorem 5.1 prove the class equality.

For a fixed first argument aa, the map y↦a⋆y=s0(y)y\mapsto a\star y=s_0(y) is injective; hence the second argument is essential. Two distinct first arguments outside the finite tag set give distinct outputs for every fixed second argument; hence the first argument is essential. Iterating the recovered s0s_0 on aa gives infinitely many elements of the generated subalgebra.

One binary operation and one constant

In addition to c0,c1,c2c_0,c_1,c_2, put c3=s02(a)c_3=s_0^2(a). These four elements are distinct. Define

x⋄y={s0(y),x=c0,s1(y),x=c1,p(y),x=c2,c2,x=c3 and V(y),c1,x=c3 and ¬V(y),x,x∉{c0,c1,c2,c3}.x\diamond y= \begin{cases} s_0(y), & x=c_0,\\ s_1(y), & x=c_1,\\ p(y), & x=c_2,\\ c_2, & x=c_3\text{ and }V(y),\\ c_1, & x=c_3\text{ and }\neg V(y),\\ x, & x\notin\{c_0,c_1,c_2,c_3\}. \end{cases}

Let C=(U;⋄,a)\mathcal{C}=(U;\diamond,a); in particular, VV is not a primitive predicate of C\mathcal{C}.

Corollary 5.4. There is a countably infinite algebra C\mathcal{C} with one binary operation and one constant such that P(C)=NP(C)\mathrm{P}(\mathcal{C})=\mathrm{NP}(\mathcal{C}). Its operation depends essentially on both arguments, and its constant generates an infinite subalgebra.

Proof. The unnamed tags are fixed ground-term values:

c1=a⋄a,c2=(a⋄a)⋄a,c3=a⋄(a⋄a).c_1=a\diamond a,\qquad c_2=(a\diamond a)\diamond a,\qquad c_3=a\diamond(a\diamond a).

We recover all the primitives of A\mathcal{A} by

s0(y)=a⋄y,s1(y)=c1⋄y,p(y)=c2⋄y,s_0(y)=a\diamond y,\qquad s_1(y)=c_1\diamond y,\qquad p(y)=c_2\diamond y,
V(y)⟺c3⋄y=c2.V(y)\Longleftrightarrow c_3\diamond y=c_2.

Each operation or test therefore requires a bounded number of C\mathcal{C}-instructions. Conversely, the case definition of ⋄\diamond uses only a bounded number of A\mathcal{A}-instructions. Apply Lemma 5.2 and Theorem 5.1. The row with first argument aa is injective in the second argument, whereas distinct first arguments outside the four-element tag set give distinct outputs for any second argument. Finally, the recovered iterates s0j(a)s_0^j(a) belong to the subalgebra generated by aa and are pairwise distinct.

Neither ⋆\star nor ⋄\diamond is associative. For example,

(a⋄a)⋄u=s1(u)≠s02(u)=a⋄(a⋄u),(a \diamond a) \diamond u = s_{1}(u) \ne s_{0}^{2}(u) = a \diamond(a \diamond u),

using the disjoint images of s0s_{0} and s1s_{1}; the same calculation applies to ⋆\star.

An associative rectangular-band operation

On U2U^{2} define

(u,v)⊙(w,z)=(u,z),J(u,v)=(v,u),(u,v) \mathbin{\odot} (w,z) = (u,z), \qquad J(u,v) = (v,u),

and, for f∈{s0,s1,p}f \in\{s_{0},s_{1},p\}, define

f^(u,v)=(f(u),f(v)).\widehat{f}(u,v) = (f(u),f(v)).

Put W(u,v)⟺V(u)W(u,v) \Longleftrightarrow V(u) and aD=(a,a)a_{\mathcal{D}} = (a,a), and let

D=(U2;⊙,J,s^0,s^1,p^,W,aD).\mathcal{D} = (U^{2}; \odot,J,\widehat{s}_{0},\widehat{s}_{1},\widehat{p},W,a_{\mathcal{D}}).

Corollary 5.5. The countably infinite structure D\mathcal{D} satisfies P(D)=NP(D)\mathrm{P}(\mathcal{D}) = \mathrm{NP}(\mathcal{D}). Its binary operation is associative and idempotent, and satisfies

x⊙y⊙x=x,x⊙y⊙z=x⊙z.x \odot y \odot x = x, \qquad x \odot y \odot z = x \odot z.

Every row and every column of its operation table has infinite image.

Proof. Let L∈NP(D)L \in\mathrm{NP}(\mathcal{D}). Replace every pair-valued data cell by two UU-valued cells. The operation ⊙\odot copies the first coordinate of its first argument and the second coordinate of its second argument; JJ swaps two cells; each f^\widehat{f} makes two calls to ff; and WW queries VV on the first coordinate. Pair equality is two equality tests. An arbitrary guessed pair is simulated by two arbitrary UU-element guesses. This gives a polynomial-time nondeterministic A\mathcal{A}-machine for the flattened language

L~={(u1,v1,…,un,vn):((u1,v1),…,(un,vn))∈L}.\widetilde{L} = \{(u_{1},v_{1},\ldots,u_{n},v_{n}) : ((u_{1},v_{1}),\ldots,(u_{n},v_{n})) \in L\}.

Inputs of odd length are rejected in the flattened language. Since P(A)=NP(A)\mathrm{P}(\mathcal{A}) = \mathrm{NP}(\mathcal{A}), this language has a deterministic polynomial-time A\mathcal{A}-decider.

To run that decider inside D\mathcal{D}, write Δu=(u,u)\Delta u = (u,u). For every input x=(u,v)x = (u,v), the two diagonal values

x⊙J(x)=Δu,J(x)⊙x=Δvx \odot J(x) = \Delta u, \qquad J(x) \odot x = \Delta v

are computed internally in bounded time. Thus the entire flattened input can be prepared in diagonal form in linear time. On diagonal data, f^(Δu)=Δf(u)\widehat{f}(\Delta u) = \Delta f(u), W(Δu)⟺V(u)W(\Delta u) \Longleftrightarrow V(u), and equality is faithful. The constant aD=Δaa_{\mathcal{D}} = \Delta a supplies the original constant. The deterministic A\mathcal{A}-decider is therefore simulated in polynomial time over D\mathcal{D}. Hence NP(D)⊆P(D)\mathrm{NP}(\mathcal{D}) \subseteq\mathrm{P}(\mathcal{D}), and the reverse inclusion is automatic.

The algebraic assertions follow by direct coordinate calculation: for x=(u,v)x = (u,v), y=(w,z)y = (w,z), and t=(r,s)t = (r,s), both bracketings of x⊙y⊙tx \odot y \odot t equal (u,s)(u,s). Also x⊙x=xx \odot x = x and x⊙y⊙x=xx \odot y \odot x = x. For a fixed row x=(u,v)x = (u,v) its image is {u}×U\{u\} \times U, and for a fixed column y=(w,z)y = (w,z) its image is U×{z}U \times\{z\}. Both are infinite. ∎

Although Δu⊙Δv=(u,v)\Delta u \odot\Delta v = (u,v), this operation does not encode pairs of arbitrary elements of the full universe U2U^{2} with recoverable components. Its recovery property is restricted to the diagonal subset. The simulation uses the lifted unary operations in the displayed signature.

A commutative associative operation

On UU define the flat meet with bottom aa by

x∧y={x,x=y,a,x≠y.x \wedge y = \begin{cases} x, & x=y,\\ a, & x\ne y. \end{cases}

Let E=(U;s0,s1,p,∧,a,V)\mathcal{E}=(U;s_0,s_1,p,\wedge,a,V).

Corollary 5.6. The countably infinite structure E\mathcal{E} satisfies P(E)=NP(E)\mathrm{P}(\mathcal{E})=\mathrm{NP}(\mathcal{E}) and contains an associative, commutative, idempotent binary operation depending essentially on both arguments.

Proof. The new operation is computed over A\mathcal{A} by one equality test and a copy or constant instruction, while every original primitive remains available. Thus Lemma 5.2 and Theorem 5.1 give the class equality.

Commutativity and idempotence follow immediately from the definition. For any three arguments, both bracketings return their common value if all three arguments are equal, and return aa otherwise. This proves associativity. If b≠ab\ne a, then b∧b=bb\wedge b=b whereas a∧b=aa\wedge b=a and b∧a=ab\wedge a=a, which proves essential dependence on each argument.

This corollary concerns the displayed expansion, which retains the unary functions and the predicate of A\mathcal{A}.

One binary operation with all rows and columns infinite

We finally compress the full signature of D\mathcal{D}. Put

F1=s^0,F2=s^1,F3=p^,F4=J.F_1=\widehat{s}_0,\qquad F_2=\widehat{s}_1,\qquad F_3=\widehat{p},\qquad F_4=J.

For j≥0j\ge0, write rj=s0j(a)r_j=s_0^j(a), and choose the six distinct diagonal tags and the auxiliary value

ti=Δri(1≤i≤4),tE=Δr5,tV=Δr6,t_i=\Delta r_i\quad(1\le i\le4),\qquad t_E=\Delta r_5,\qquad t_V=\Delta r_6,
k=r7,κ=Δk.k=r_7,\qquad\kappa=\Delta k.

These are fixed ground-term values in D\mathcal{D}, and kk is different from the first coordinate of every tag. Define

E(u,v)=(k,v)=κ⊙(u,v),G(x)={F2(x),W(x),F1(x),¬W(x).E(u,v)=(k,v)=\kappa\odot(u,v),\qquad G(x)= \begin{cases} F_2(x), & W(x),\\ F_1(x), & \neg W(x). \end{cases}

and set

x∘y={Fi(x),y=ti(1≤i≤4),E(x),y=tE,G(x),y=tV,x⊙y,y∉{t1,t2,t3,t4,tE,tV}.x\circ y= \begin{cases} F_i(x), & y=t_i\quad(1\le i\le4),\\ E(x), & y=t_E,\\ G(x), & y=t_V,\\ x\odot y, & y\notin\{t_1,t_2,t_3,t_4,t_E,t_V\}. \end{cases}

Let

F=(U2;∘,aD,t1,t2,t3,t4,tE,tV,κ).\mathcal{F}=(U^2;\circ,a_{\mathcal{D}},t_1,t_2,t_3,t_4,t_E,t_V,\kappa).

The final signature contains one binary operation and eight constants, with no unary function or primitive predicate.

Corollary 5.7. The countably infinite algebra F\mathcal{F} satisfies P(F)=NP(F)\mathrm{P}(\mathcal{F})=\mathrm{NP}(\mathcal{F}). Every row and every column of its binary operation has infinite image, and its named constants generate an infinite subalgebra.

Proof. The case definition computes ∘\circ in bounded time over DD, and all named constants of F\mathcal{F} are fixed ground-term values there. Conversely, the unary operations are recovered by

Fi(x)=x∘ti,E(x)=x∘tE.F_i(x)=x\circ t_i,\qquad E(x)=x\circ t_E.

Because E(y)E(y) has first coordinate kk, it cannot equal any of the six tags. Therefore the original product is recovered by

x⊙y=x∘(y∘tE).x\odot y=x\circ(y\circ t_E).

Indeed, the right-hand side is x∘E(y)=(x1,y2)x\circ E(y)=(x_1,y_2). The predicate is recovered by

W(x)⟺x∘tV=x∘t2.W(x)\Longleftrightarrow x\circ t_V=x\circ t_2.

For the false case, F1(x)≠F2(x)F_1(x)\ne F_2(x) follows from the disjoint images of s0s_0 and s1s_1. Thus every primitive of DD is simulated in bounded time. Lemma 5.2 and Corollary 5.5 imply the asserted class equality.

For fixed xx, all arguments y=(k,d)y=(k,d), d∈Ud\in U, are outside the tag set and give the distinct outputs (x1,d)(x_1,d); hence each row has infinite image. An ordinary column yy has image U×{y2}U\times\{y_2\}. Each special column also has infinite image: F1,F2F_1,F_2 are injective, F3F_3 is surjective, F4F_4 is bijective, and EE has image {k}×U\{k\}\times U. Finally, GG is injective, since each of its branches is injective and the two branch images are disjoint. This deals with all columns. Iterating the recovered F1F_1 on aDa_D gives infinitely many pairwise distinct ground-term values. □\square

The operation ∘\circ is not associative. Choose u≠vu\ne v, let x=(u,u)x=(u,u) and y=(u,v)y=(u,v), and use the interchange tag t4t_4. Both yy and J(y)J(y) are off the diagonal and therefore are not tags. Consequently,

(x∘y)∘t4=(v,u),x∘(y∘t4)=(u,u).(x\circ y)\circ t_4=(v,u),\qquad x\circ(y\circ t_4)=(u,u).

These examples show that essential dependence on both arguments, infinite rows and columns, and infinite generation by the named constants are compatible with P=NPP=NP. The obstruction proved earlier requires a way of recovering both arbitrary input elements from one encoded element. By Proposition 2.5, all five positive examples also satisfy PH=P\mathrm{PH}=P, and every fixed level of their mixed hierarchies equals PP.

Concluding observations

The negative and positive results identify a precise distinction. In Malcev’s algebra the binary pairing function retains both arbitrary arguments, and the projections make them available at unit cost. Theorem 4.2 shows that omitting projections does not rescue a possible collapse. By contrast, the operations of the positive examples either dispatch among unary instructions or discard information from their inputs. Essential dependence on both arguments, associativity in an expanded signature, and infinite row and column images do not by themselves supply a recoverable pairing of the full universe.

The five constructions all inherit their collapse from the unary structure. No independent forcing construction is needed. Their displayed signatures are part of their statements: the rectangular-band and flat-meet examples retain specified unary operations, while the two compressed algebras C\mathcal{C} and F\mathcal{F} retain no primitive predicates and have nonassociative binary operations.

Theorem 3.6 applies to every final interpretation of the additional primitives. It therefore rules out a truth-predicate construction on the free binary-tree algebra regardless of whether that predicate is defined by recursion, a genericity argument, or another method. The contradiction uses finite traces only and has no dependence on countability or well-foundedness beyond what is needed to describe the particular free-tree example. Standard arithmetic (N;+,⋅,0,1)(\mathbb{N}; +, \cdot, 0, 1) illustrates the obstruction through its first-order definable Cantor pairing and projections. The trace argument applies to the auxiliary definitional expansion, and the graph simulation transfers the contradiction to the original signature and every finite expansion, including an arbitrary predicate VV. For structures with primitive pairing and projections, or fixed terms representing them, polynomial-time access to a packed trace places deterministic exponential time in Σ2S,B\Sigma^{S,B}_{2}, whereas a hypothetical P=NP\mathrm{P} = \mathrm{NP} would collapse that mixed class, and the entire polynomial hierarchy, to P. The comparison with Tarski separates this computational obstruction from both external truth for the base language and the direct diagonal obstruction to existential truth in the expanded arithmetic language. In the elementary arithmetic signature {+,mod⁡,exp⁡2,0,1}\{+, \operatorname{mod}, \operatorname{exp}_{2}, 0, 1\}, the substitution-basis theorem provides fixed terms for pairing and its projections, so the trace inclusion holds without a collapse hypothesis. With elementary syntax coding, the same term representation of diagonal substitution yields the quantifier-free truth obstruction of Proposition 4.8.

Acknowledgments

This paper was produced in an AI-assisted workflow. AI assistants helped explore candidate constructions, draft proofs, and write software for numerical experiments.

References

  1. [1]L. Blum, M. Shub and S. Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bulletin of the American Mathematical Society (N.S.) 21 (1989), no. 1, 1–46. doi:10.1090/S0273-0979-1989-15750-9.DOI
  2. [2]L. Blum, F. Cucker, M. Shub and S. Smale, Complexity and Real Computation, Springer-Verlag, New York, 1998. doi:10.1007/978-1-4612-0701-6.DOI
  3. [3]O. Bournez, F. Cucker, P. Jacobé de Naurois and J.-Y. Marion, Implicit complexity over an arbitrary structure: Quantifier alternations, Information and Computation 204 (2006), no. 2, 210–230. doi:10.1016/j.ic.2005.07.005.
  4. [4]A. K. Chandra, D. C. Kozen and L. J. Stockmeyer, Alternation, Journal of the ACM 28 (1981), no. 1, 114–133. doi:10.1145/322234.322243.DOI
  5. [5]S. A. Cook, The complexity of theorem-proving procedures, in Proceedings of the Third Annual ACM Symposium on Theory of Computing, ACM, New York, 1971, pp. 151–158. doi:10.1145/800157.805047.DOI
  6. [6]H. Fournier and P. Koiran, Lower bounds are not easier over the reals: inside PH, in Automata, Languages and Programming (ICALP 2000), Lecture Notes in Computer Science 1853, Springer, Berlin, 2000, pp. 832–843. doi:10.1007/3-540-45022-X_70.DOI
  7. [7]C. Gaßner, A structure with P = NP, in Logical Approaches to Computational Barriers (CiE 2006), Informal Proceedings, Computer Science Report Series, University of Wales Swansea, Report CSR 7 (2006), pp. 85–94.
  8. [8]C. Gaßner, Oracles and relativizations of the P =? NP question for several structures, Journal of Universal Computer Science 15 (2009), no. 6, 1186–1205. doi:10.3217/jucs-015-06-1186.
  9. [9]J. B. Goode, Accessible telephone directories, The Journal of Symbolic Logic 59 (1994), no. 1, 92–105. doi:10.2307/2275252.DOI
  10. [10]J. Hartmanis and R. E. Stearns, On the computational complexity of algorithms, Transactions of the American Mathematical Society 117 (1965), 285–306. doi:10.1090/S0002-9947-1965-0170805-7.DOI
  11. [11]A. Hemmerling, P = NP for some structures over the binary words, Journal of Complexity 21 (2005), no. 4, 557–578. doi:10.1016/j.jco.2005.02.001.
  12. [12]P. Koiran, Computing over the reals with addition and order, Theoretical Computer Science 133 (1994), no. 1, 35–47. doi:10.1016/0304-3975(93)00063-B.
  13. [13]S. Kripke, Outline of a theory of truth, The Journal of Philosophy 72 (1975), no. 19, 690–716. doi:10.2307/2024634.DOI
  14. [14]A. I. Mal’cev, Axiomatizable classes of locally free algebras of certain types, Sibirskij Matematicheskij Zhurnal 3 (1962), no. 5, 729–743 (in Russian). Math-Net.Ru: smj4864.
  15. [15]Yu. V. Matiyasevich, Diophantine representation of enumerable predicates, Mathematics of the USSR-Izvestiya 5 (1971), no. 1, 1–28. doi:10.1070/IM1971v005n01ABEH001004.
  16. [16]S. Mazzanti, Plain Bases for Classes of Primitive Recursive Functions, Mathematical Logic Quarterly 48 (2002), no. 1, 93–104. doi:10.1002/1521-3870(200201)48:1<93::AID-MALQ93>3.0.CO;2-8.
  17. [17]K. Meer, A note on a P ≠ NP result for a restricted class of real machines, Journal of Complexity 8 (1992), no. 4, 451–453. doi:10.1016/0885-064X(92)90007-X.
  18. [18]K. Meer, Real number models under various sets of operations, Journal of Complexity 9 (1993), no. 3, 366–372. doi:10.1006/jcom.1993.1023.
  19. [19]B. Poizat, Les petits cailloux: une approche modèle-théorique de l’algorithmie, Nur al-Mantiq wal-Ma’rifah, vol. 3, Aléas, Lyon, 1995.
  20. [20]B. Poizat, Une tentative malheureuse de construire une structure éliminant rapidement les quanteurs, in P. G. Clote and H. Schwichtenberg (eds.), Computer Science Logic (CSL 2000), Lecture Notes in Computer Science 1862, Springer, Berlin, 2000, pp. 61–70. doi:10.1007/3-540-44622-2_4.
  21. [21]M. Prunescu, Structure with fast elimination of quantifiers, The Journal of Symbolic Logic 71 (2006), no. 1, 321–328. doi:10.2178/jsl/1140641177.DOI
  22. [22]M. Prunescu, Fast quantifier elimination means P = NP, in Logical Approaches to Computational Barriers (CiE 2006), Lecture Notes in Computer Science 3988, Springer, Berlin, 2006, pp. 459–470. doi:10.1007/11780342_47.
  23. [23]M. Prunescu, L. Sauras-Altuzarra and J. M. Shunia, A minimal substitution basis for the Kalmár elementary functions, Journal of Logic and Computation 36 (2026), no. 3, Article exag010. doi:10.1093/logcom/exag010.
  24. [24]L. J. Stockmeyer, The polynomial-time hierarchy, Theoretical Computer Science 3 (1976), no. 1, 1–22. doi:10.1016/0304-3975(76)90061-X.DOI
  25. [25]A. Tarski, The semantic conception of truth and the foundations of semantics, Philosophy and Phenomenological Research 4 (1944), no. 3, 341–376. doi:10.2307/2102968.
  26. [26]A. Tarski, The concept of truth in formalized languages, in Logic, Semantics, Metamathematics: Papers from 1923 to 1938, translated by J. H. Woodger, Clarendon Press, Oxford, 1956, pp. 152–278.

Paper details

vlnc:W_2vc9ycm7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI assistants

View statement
Looking for related papers…
Contents