From a very naive point of view of someone who haven't studied complexity theory in depth, I am wondering whether the theorems that APSPACE=EXPTIME and AP=PSPACE have any derived results on separating P from PSPACE, i.e. P=PSPACE implying AP=APSPACE and thus violating the Time Hierarchy and Space Hierarchy theorems. I would like any references discussing these relationships and why does this separation not happen or why is deciding this separation hard by discussing the alternating complexity classes and their relationship to their deterministic and probabilistic variants or alternatively any attempts on deriving alternating variants of Time Hierarchy and Space Hierarchy theorems.



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.