Does there exist a language which is PSPACE-complete and regular? (reduction is polynomial with regard to time).

Correct answer here is "unknown". I can't prove it. Can you help me?


There exists a PSPACE-complete regular language if and only if P=PSPACE, which is unknown.

In fact, we can say even more: the language $\{1\}$ is PSPACE-complete if and only if P=PSPACE.

  • $\begingroup$ Is it about that each regular language is in $P$ ? $\endgroup$ – Haskell Fun Aug 27 '17 at 9:16
  • $\begingroup$ This is definitely part of the matter. $\endgroup$ – Yuval Filmus Aug 27 '17 at 9:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.