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.


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.