Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-207 | 23rd September 2026 03:37

Towards an Interesting VPSPACE-complete Problem

RSS-Feed

Abstract:

We introduce a variant of a polynomial family called $\TQBFfamily$ obtained from `arithmetization' of the popular $\PSPACE$-complete problem - $\TQBF$. This polynomial family has several nice characteristics such as: $\TQBFfamily \in \VPSPACE_b$, where $\VPSPACEb$ is the `bounded' algebraic version of $\PSPACE$, it is \emph{self-testable}, it captures the computational power of $\PSPACE$ and others.
Although the first version of $\TQBFfamily$ appeared in an earlier work of Carmosino et al. (RANDOM, 2015), we believe that our presentation is cleaner and simpler.

Building on that, we construct another polynomial family, $\TPfamily \in \VPSPACE_b$, by mixing $\TQBFfamily$ and $\Permfamily$, the family of the Permanent polynomial. While we are unable to prove that $\TPfamily$ is $\VPSPACE_b$-complete,
we show that it has many traits of $\VPSPACE_b$-completeness as well as several important consequences in computational complexity, which are listed below.
\begin{itemize}
\item We show that if $\TPfamily$ can be computed by circuits from a circuit class $\Ccal \subseteq \VNP$ then $\VPSPACE_b \subseteq \Ccal$.
\item We also conclude that if $\Ccal$ has a black-box $\PIT$ algorithm that uses sub-polynomial space, then $\TPfamily$ cannot be computed by polynomial-size arithmetic circuits from $\Ccal$.
\item Finally, we prove a version of a Karp-Lipton style collapse theorem by showing that if $\TQBFfamily$ has ``small'' arithmetic circuits then $\PSPACE$ collapses to $\NP$ with a $\PIT$ oracle (i.e. $\PSPACE \subseteq \NP^{\PIT}$).
\end{itemize}

The second result makes a partial progress towards the resolution of an open problem posed in a survey by Shpilka \& Yehudayoff (Foundations and Trends in Theoretical Computer Science, 2010).
As a corollary, we give an ``inconsistent triad'' of $\PIT$ and circuit lower bounds, similar to the one given by Kabanets and Impagliazzo (Computational Complexity, 2004).
Finally, we note that Malod gave complete polynomial families for $\VPSPACE$, the `unbounded' algebraic version of $\PSPACE$ (Foundations of Computation Theory, 2011).



ISSN 1433-8092 | Imprint