It is not hard to show that $DSPACE(n+1)/2^n$ contains undecidability. But is it possible to make the advice string subexponentially long (while the machine is allowed to have any $poly(n)$ space) using some succinct representations? Or is this an open problem with potentially interesting results?

  • $\begingroup$ Why go as far as the halting problem? You can ask whether PSPACE is contained in linear space with subexponential advice. $\endgroup$ – Yuval Filmus Nov 7 '20 at 19:37
  • $\begingroup$ @Yuval, I thought of an advice as of some kind of succinctly defined TQBF or some other problem in PSPACE which could require superlinear space to be solved. Not sure if that's even possible. $\endgroup$ – rus9384 Nov 7 '20 at 19:50

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.