P vs. PSPACE

P vs. PSPACE

Definitions and mathematical statement

For an input of length $n$, time counts computation steps and space counts work-tape cells. Define \[ \mathsf P=\bigcup_{k\ge1}\mathsf{DTIME}(n^k),\qquad \mathsf{PSPACE}=\bigcup_{k\ge1}\mathsf{DSPACE}(n^k). \] Machines must halt and decide their language correctly on every input. Determine whether these classes coincide. An algorithm with polynomial space and exponential time does not establish membership in $\mathsf P$.

Formulation and concept references: [S1].

Short English statement

Can every decision problem solvable with polynomially much memory also be solved in polynomially much time?

Research attempt

Scope and literature check.

This unresolved attempt by GPT-6 Astra Ultra was prepared on 27 September 2026. Its method was to examine the configuration graph of a polynomial-space computation, seek a compact way to accelerate many transitions, and test the proposed representations on explicit examples. The target concerns all halting deciders with one fixed polynomial space bound per machine. A negative answer needs one such language outside every polynomial time bound.

Williams [S2], Theorem 1.1, proves the multitape simulation \[ \mathsf{TIME}[t(n)]\subseteq \mathsf{SPACE}\left[\sqrt{t(n)\log t(n)}\right] \qquad(t(n)\ge n). \] Corollary 1.2 gives time lower bounds near the square of a constructible space bound. These are fixed-power separations, not a separation from the union of all polynomial time bounds. The MFCS 2026 abstract [S3] surveys that result and subsequent developments; it is not used to claim an unproved inverse simulation from polynomial space to polynomial time. The configuration-graph background is also discussed in [E1], Chapter 4. The arguments below are proved explicitly and are not claimed to be new complexity theorems.

Attack plan: compress a deterministic trajectory.

A deterministic computation using $s$ configuration bits has at most $2^s$ configurations. A halting trajectory cannot repeat a nonhalting configuration: once repeated, determinism would force a loop. Thus exponential simulation is available with polynomial memory, but the central issue is whether the trajectory can be skipped in large blocks.

Two candidate block representations are a circuit for the iterated successor and an algebraic map over $\mathbb F_2$. The affine case admits a complete polynomial-time algorithm for an absorbing target. General Boolean circuits already encompass the full original difficulty; low-degree coordinate polynomials need not stay small when expanded under composition.

Lemma 14.1: the succinct functional-graph target.

Consider the following language of encoded triples $(F,a,t)$. The input contains a Boolean circuit for a total map $F:\{0,1\}^s\to\{0,1\}^s$, together with $a,t\in\{0,1\}^s$. Accept exactly when $F(t)=t$ and $F^j(a)=t$ for some integer $j\ge0$. This language is PSPACE-complete under polynomial-time many-one reductions.

Membership. Check $F(t)=t$. Starting at $a$, evaluate successive states and test whether they equal $t$. If the first $2^s$ states, indexed $0$ through $2^s-1$, omit $t$, some state repeats before a first possible later visit, and determinism rules that visit out. A binary counter with $s+1$ bits suffices to implement this bound. Circuit evaluation and the current state require space polynomial in the input encoding length. Therefore the decision procedure is in PSPACE; its time need not be polynomial.

Hardness. Fix a language $L$ in PSPACE and a halting deterministic machine $M$ deciding it in at most $p(n)$ work cells. On a fixed input $x$, encode a configuration by its work-tape contents, head positions, and state, using $s=\operatorname{poly}(|x|)$ bits. The fixed input $x$ is hardwired into a polynomial-size circuit computing one transition. Validity of the configuration encoding and head positions is also checked by polynomial-size circuits. Reserve two additional tagged configurations for acceptance and rejection. Map an accepting machine configuration to the acceptance tag, a rejecting one to the rejection tag, and both tags to themselves. Invalid encodings can map to the rejection tag. These tests and updates are local or polynomial-size comparisons, so the resulting total circuit is constructible in polynomial time in $|x|$. Let $a$ encode the initial configuration and $t$ be the acceptance tag. The resulting trajectory reaches $t$ precisely when $M$ accepts $x$, and $t$ is absorbing. This proves the reduction.$\square$

Thus a general polynomial-time algorithm for this particular succinct functional-graph problem would prove $\mathsf P=\mathsf{PSPACE}$. A long trajectory alone would not prove the opposite: the decision problem allows an algorithm to determine the destination without visiting every state. For example, a binary counter takes exponentially many increments to reach a specified high count, but its order and destination are easily understood arithmetically.

Lemma 14.2: a complete affine special case.

Suppose $F(v)=Av+b$ over $\mathbb F_2$, where $A\in\mathbb F_2^{s\times s}$ and $b\in\mathbb F_2^s$ are explicitly given, and suppose $F(t)=t$. Then \begin{equation}\label{wsref-0-61-31-34-3a-61-66-66-69-6e-65} \exists j\ge0:\ F^j(a)=t \quad\Longleftrightarrow\quad A^s(a-t)=0. \end{equation} The right side is computed in $O(s^3)$ field operations and $O(s^2)$ working bits by at most $s$ matrix-vector multiplications.

Proof. Since $At+b=t$, $F(v)-t=A(v-t)$, and induction gives $F^j(a)-t=A^j(a-t)$. Write $K_j=\ker A^j$, with $K_0=\{0\}$. The subspaces satisfy $K_j\subseteq K_{j+1}$. If $K_j=K_{j+1}$, then $A^{j+2}v=0$ implies $Av\in K_{j+1}=K_j$, whence $v\in K_{j+1}$. Thus $K_{j+2}=K_{j+1}$ and the chain stays constant thereafter. There can be at most $s$ strict dimension increases, so it has stabilized by $K_s$. Consequently $A^j(a-t)=0$ for some $j$ exactly when $a-t\in K_s$. The computation bound follows from $s$ products, each costing $O(s^2)$ field operations.$\square$

The absorbing-target hypothesis is essential to this proof. An arbitrary orbit-membership question for affine maps is not being silently identified with kernel membership. Moreover the result uses explicit coefficients; no algorithm for recognizing or discovering a hidden affine conjugacy of an arbitrary succinct graph has been supplied.

A useful interpretation is that the part of an affine orbit that can die at a fixed point is governed by an ascending chain of kernels. Its dimension is the potential function limiting the relevant evolution. This succeeds even though the same affine map may have long cycles elsewhere. A potential function for general Boolean transitions with an analogous polynomial bound would be a substantive missing ingredient.

Testing polynomial composition as a generalization.

Every Boolean function has a unique multilinear polynomial over $\mathbb F_2$. It is tempting to store each successor coordinate in this form and square the transition by substitution, reducing $z^2$ to $z$. The following family shows that an expanded monomial representation can already become exponential after logarithmically many simple updates.

Let $k$ be a power of two. Use $2k$ fixed leaf coordinates $x_1,y_1,\ldots,x_k,y_k$, a coordinate $u_i$ for each pair, and one coordinate for every internal node of a balanced binary tree with leaves $u_i$. Define a synchronous map $G$ as follows: the $x_i,y_i$ coordinates stay fixed, $u_i$ is replaced by $x_i+y_i$, and each tree-node coordinate is replaced by the product of its two child coordinates. There are $4k-1$ coordinates and each update polynomial has degree at most two. The entire map has a Boolean circuit of size $O(k)$.

After $1+\log_2 k$ iterations, the root coordinate is \begin{equation}\label{wsref-0-61-31-34-3a-65-78-70-61-6e-73-69-6f-6e} \prod_{i=1}^k(x_i+y_i) =\sum_{\varepsilon\in\{0,1\}^k} \prod_{i=1}^k \begin{cases}x_i,&\varepsilon_i=0,\\y_i,&\varepsilon_i=1. \end{cases} \end{equation} This follows by induction on the level of the tree: after the first update the leaves of that tree contain the desired pair sums, and each successive update propagates their products one level. Initial values of the auxiliary coordinates no longer affect the root at the stated time. The $2^k$ monomials in the expansion are squarefree and distinct, since each selects one variable from each disjoint pair. None cancel over $\mathbb F_2$. Uniqueness of the multilinear polynomial therefore forces $2^k$ stored monomials in an explicit expansion.

This falsifies the proposed universal polynomial bound for that representation. It does not lower-bound the size of circuits for the iterates: the factored expression on the left has a circuit with $O(k)$ gates. Keeping factorization repairs this example. The remaining question is whether such compact factorizations or other summaries can always be found and manipulated for arbitrary transitions. Simply writing the formal composition $F^{2^{r+1}}=F^{2^r}\circ F^{2^r}$ supplies two copies of the prior circuit, so the direct construction doubles its size at each stage. It gives no uniform polynomial bound after $s$ stages.

Verification and boundary cases.

The companion script exhaustively checks (a14:affine) for every binary matrix of dimensions $1,2,3$, every translation $b$, every fixed point $t$, and every starting point $a$, comparing the kernel test with direct orbit exploration until repetition. It also expands (a14:expansion) for $k=1,2,4,8$, verifies $2^k$ distinct monomials, and compares its truth values with the factored expression through $k=4$. The tests are finite checks of these lemmas, not checks of the open separation.

If $a=t$, the algorithm accepts immediately and $A^s(a-t)=0$. A permutation matrix has zero kernel, so only $a=t$ can reach the absorbing target; a nilpotent matrix reaches it from every translated starting point. These opposite cases agree with the lemma. The circuit reduction has only one successor per state, so no nondeterminism is concealed in its hardness.

Remaining gap and outcome.

UNRESOLVED. The proved special-case algorithm uses a kernel chain whose dimension bounds all progress toward a fixed point. The attempted expanded-polynomial extension fails on an explicit linear-size family. A positive solution still needs polynomial-time reachability for arbitrary succinct deterministic transitions, or a different equivalent algorithm. A negative solution needs a lower bound against all polynomial-time deciders, not merely against simulation or monomial expansion. Concrete continuations would seek a richer invariant preserved under composition, bound the total size and cost of its updates, and test it on nonlinear circuits encoding polynomial-space machines. None of those general bounds has been established.

Sources

• S1 Walter S. Brainerd and Lawrence H. Landweber et al., Computability, Decidability, Complexity, third edition. https://art.torvergata.it/bitstream/2108/32769/60437/ComputabilityDecidabilityComplexity.pdf. Formulation source.
• S2 Simulating Time With Square-Root Space — Ryan Williams, February 24, 2025. https://eccc.weizmann.ac.il/report/2025/017/download. Further reference; not a proof endorsement.
• S3 Some Recent Developments in Space Complexity — R. Ryan Williams, MFCS 2026. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.3. Further reference; not a proof endorsement.
• S4 Some conditions implying if P=NP then P=PSPACE — Ismael Rodriguez (February 10, 2026). https://arxiv.org/abs/2602.10073. Further reference; not a proof endorsement.
• E1 Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, web draft, 8 January 2007, Chapter 4, space complexity and configuration graphs. https://theory.cs.princeton.edu/complexity/book.pdf. Background definitions; consulted 27 September 2026. The restricted functional-graph reduction and affine algorithm used here are proved in this attempt.

P vs. PSPACE

Definitions and mathematical statement

For an input of length $n$, time counts computation steps and space counts work-tape cells. Define \[ \mathsf P=\bigcup_{k\ge1}\mathsf{DTIME}(n^k),\qquad \mathsf{PSPACE}=\bigcup_{k\ge1}\mathsf{DSPACE}(n^k). \] Machines must halt and decide their language correctly on every input. Determine whether these classes coincide. An algorithm with polynomial space and exponential time does not establish membership in $\mathsf P$.

Formulation and concept references: [S1].

Short English statement

Can every decision problem solvable with polynomially much memory also be solved in polynomially much time?

Research attempt

Current frontier.

Research check: 27 September 2026. Williams's time-to-space simulation gives $\mathsf{TIME}[t]\subseteq\mathsf{SPACE}[\sqrt{t\log t}]$ in the multitape setting of Theorem 1.1, with the stated constructibility and $t\geq n$ conventions. Its fixed-exponent consequences do not separate the unions of all polynomial time and all polynomial space. [S2]. The 2026 MFCS account discusses this development, not a proof that the two classes in this entry differ. [S3]. We investigate whether compact iteration of a transition map can remove the exponential time of a polynomial-space computation, and then test whether the new space simulation can be bootstrapped instead.

Attack route.

A configuration graph has exponentially many vertices but a short local transition rule. Repeated squaring is promising only if the iterated transition maps stay in an efficiently constructible representation. Alternatively, stronger uniform time-to-space compression could combine with the space hierarchy. The first route needs a closure theorem under composition; the second needs a substantially stronger simulation than the theorem just quoted. We keep the two missing statements separate.

Attempt: an exact succinct-iteration target.

Define a total decision problem $\mathcal I$. An instance consists of a Boolean circuit $C$ computing $f_C:\{0,1\}^w\to\{0,1\}^w$, an initial state $z$, a nonnegative integer $T$ in binary, and a coordinate $i$. The answer is $(f_C^T(z))_i$; malformed instances are rejected. Circuit encodings explicitly list inputs and outputs, so $w$ is bounded by the input length. This problem belongs to $\mathsf{PSPACE}$: keep the current $w$-bit state, a $\log(T+1)$-bit counter, and enough workspace to evaluate $C$. The loop halts after $T$ iterations, even when $T$ is exponential in its encoded length.

Conversely, let a fixed deterministic machine $M$ decide a language in space $n^k$. Encode its configurations on input $x$ in $w=n^{O(1)}$ bits, using extra padding to include all state, head, and work-tape information. A circuit $C_x$ of size polynomial in $w+|x|$ computes one transition; invalid encodings can map to themselves. Make accepting and rejecting configurations absorbing and add an acceptance flag coordinate. The start configuration $z_x$ is explicitly computable. A halting deterministic computation cannot revisit a nonhalting configuration, so it halts within $2^w$ steps. Therefore \[ x\in L(M)\quad\Longleftrightarrow\quad (f_{C_x}^{\,2^w}(z_x))_{\rm accept}=1. \tag{14.1} \] The binary encoding of $2^w$ has only $w+1$ bits. This is a polynomial-time reduction, with $M$ fixed and $x$ varying. It proves directly that \[ \mathcal I\in\mathsf P\quad\Longleftrightarrow\quad \mathsf P=\mathsf{PSPACE}. \tag{14.2} \] This standard configuration idea is used here as an explicit test bed, not as an independently easier reformulation. The surrounding configuration and simulation model is discussed in [S2], Sections 1 and 5.

Attempt: a representation in which iteration does work.

For the special case $f(z)=Az+b$ over ${\mathbb{F}}_2$, augment the state by $1$ and put \[ \widetilde A=\begin{pmatrix}A&b\\0&1\end{pmatrix}. \qquad \begin{pmatrix}f^T(z)\\1\end{pmatrix} =\widetilde A^{\,T}\begin{pmatrix}z\\1\end{pmatrix}. \tag{14.3} \] Repeated squaring uses $O(\log(T+1))$ matrix multiplications, each with $O((w+1)^3)$ field operations. All coefficients are bits. Thus affine succinct iteration is polynomial-time in the encoded parameters, including binary $T$. This really does handle exponential iteration counts, but only because the representation has a dimension closed under composition.

For general circuits, the same notation hides duplication. If $C_j$ computes $f^{2^j}$, constructing $C_{j+1}$ by substituting $C_j$ into a second copy gives a size recurrence of the form $S_{j+1}\leq2S_j+O(w)$. This construction can grow as $2^j$, rather than polynomially in $j$. Merely drawing two calls to the same subroutine is not a Boolean circuit of size one call: they are evaluated on different inputs. Fan-out shares a value, not a function evaluated at another argument.

A degree bound also fails as a universal invariant. Introduce registers $z,a_1,\ldots,a_r,t$, with a clock $t$ selecting the next update, and perform $z\leftarrow za_t$. Starting at $z=1$, after $r$ updates one has $z=a_1\cdots a_r$. Each selected update is quadratic in the data, but the multilinear degree of its composition is $r$. This does not prove large circuit size: the product has a small circuit. It does show why bounded degree alone cannot justify an affine-style closure argument.

Attempt: the hierarchy route and its quantifiers.

Here is a sufficient stronger simulation, written as a conditional statement. Suppose that for every $\varepsilon>0$ and every suitable time bound $t\geq n$, \[ \mathsf{TIME}[t]\subseteq\mathsf{SPACE}[t^{\varepsilon}]. \tag{14.4} \] Then $\mathsf P\ne\mathsf{PSPACE}$. Indeed, by the deterministic space hierarchy choose $L\in\mathsf{SPACE}[n^2]\setminus\mathsf{SPACE}[n]$. If $\mathsf P=\mathsf{PSPACE}$, this same $L$ has time $O(n^k)$ for some fixed $k$. Choose $0<\varepsilon<1/k$ in $14.4$; constants and the constructible time bound can be enlarged harmlessly. The resulting space bound is $O(n^{k\varepsilon})\subseteq O(n)$, a contradiction. This quantifier pattern is the strengthened-simulation direction identified in [S2], Section 5. It does not follow by applying Theorem 1.1 repeatedly to its own output.

Stress test.

To expose the failed bootstrap, let the first simulator use $s=O(\sqrt{t\log t})$ work cells. A halting computation with this much space need only have the crude configuration-count time bound $2^{O(s+\log n)}$. Applying the time-to-space theorem to that implementation charges its new running time, not the original $t$. Substituting the crude bound gives an exponentially large quantity, not $t^{1/4}$. No polynomial-time preservation theorem for the first simulator has been supplied. This is an accounting obstruction to the proposed inference, not a lower bound on the best possible simulator.

Likewise, separation of $\mathsf{SPACE}[n]$ from a particular $\mathsf{TIME}[n^a]$ does not separate $\mathsf{PSPACE}$ from every polynomial time bound. The exponent of a putative decider is unrestricted. The affine algorithm cannot process the nonlinearity of an arbitrary configuration circuit, and finite experiments on randomly chosen maps do not address the worst-case uniform circuit family in $14.1$. A conditional argument using $\mathsf P\ne\mathsf{NP}$ would already settle this entry negatively because $\mathsf P\subseteq\mathsf{NP}\subseteq\mathsf{PSPACE}$; it would not be an unconditional separation.

Outcome.

Outcome: Exploratory approach with unresolved gap. The notebook supplies an exact succinct-iteration reduction, a genuine polynomial-time affine special case, and a quantified stronger-simulation condition that would separate the classes. Neither efficient closure of general transition circuits nor $14.4$ is established. The attempted bootstrap of square-root-space simulation fails because it reuses the wrong time parameter. These auxiliary deductions are not claimed to be historically new or to resolve the original class equality.

Sources

• S1 Walter S. Brainerd and Lawrence H. Landweber et al., Computability, Decidability, Complexity, third edition. https://art.torvergata.it/bitstream/2108/32769/60437/ComputabilityDecidabilityComplexity.pdf. Catalogue formulation source.
• S2 Simulating Time With Square-Root Space — Ryan Williams, February 24, 2025. https://eccc.weizmann.ac.il/report/2025/017/download. Catalogue research/status reference; not a proof endorsement.
• S3 Some Recent Developments in Space Complexity — R. Ryan Williams, MFCS 2026. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.3. Catalogue research/status reference; not a proof endorsement.
• S4 Some conditions implying if P=NP then P=PSPACE — Ismael Rodriguez (February 10, 2026). https://arxiv.org/abs/2602.10073. Catalogue research/status reference; not a proof endorsement.