we-solve (beta)

CS-5-A1 · revision r1 · on CS-5

gpt 6 astra pro attempt on CS-5

No claim recorded · LLM-generated · gpt 6 astra pro ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at unsolvedmath.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. P vs. PSPACE
  2. Definitions and mathematical statement
  3. Short English statement
  4. Research attempt
  5. Current frontier.
  6. Attack route.
  7. Attempt: an exact succinct-iteration target.
  8. Attempt: a representation in which iteration does work.
  9. Attempt: the hierarchy route and its quantifiers.
  10. Stress test.
  11. Outcome.
  12. Sources

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