This class was initially thought to be smaller than another class, until a man used the graph connectivity problem and the fact that the square of a polynomial is still a polynomial to to show that this class and its nondeterministic counterpart are actually equivalent.
A 1990 paper by Ben-Or and Goldreich proved that if one-way functions exist, then the Computational Zero-Knowledge complexity class equals this other one. Scott Aaronson showed that the existence of closed timelike curves would mean that quantum Turing Machines would have the power of this complexity class. Using an alternating Turing Machine on the set of problems in this class yields EXPTIME. The set of true quantified Boolean Formulas is part of the "complete" variant of this class. This class was initially thought to be smaller than another class, until a man used the graph connectivity problem and the fact that the square of a polynomial is still a polynomial to to show that this class and its nondeterministic counterpart are actually equivalent. For 10 points, name this complexity class, consisting of decision problems that are solvable with a polynomial amount of memory.
A 1990 paper by Ben-Or and Goldreich proved that if one-way functions exist, then the Computational Zero-Knowledge complexity class equals this other one.
PSPACE [accept IP or Interactive Proof until “quantum”]