Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers

Abhijit S. Mudigonda, R. Ryan Williams

A line of work initiated by Fortnow in 1997 has proven model-independent time-space lower bounds for the $\mathsf{SAT}$ problem and related problems within the polynomial-time hier…