Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > VALIANT'S COMPLEXITY CLASSES:
Reports tagged with Valiant's Complexity Classes:
TR26-207 | 23rd September 2026
Marco Carmosino, Nikhil Gupta, Ilya Volkovich

Towards an Interesting VPSPACE-complete Problem

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 ... more >>>




ISSN 1433-8092 | Imprint