14
$\begingroup$

It seems that encoding an NP-complete problem succinctly often makes it nexptime-complete. For instance, 3SAT or HAMILTONIAN PATH become NEXPTIME-complete when the encoding is succint, eg using circuits.

Can a similar approach be taken for PSPACE-complete problems? For instance, do we get EXPSPACE-completeness if QBF or GENERALIZED GEOGRAPHY are encoded using circuits?

I see Ryan Williams has a paper discussing SUCCINT-QBF but I am not familiar enough with complexity theory to understand it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.