Is there some example of a PSPACE problem that we can show PSPACE-hard under NP reduction, but we do not know a proof of PSPACE-hardness under P reduction ?

To be more precise, the NP reduction I am referring to is of the following kind: take your problem A that you want to show PSPACE-complete. You show that given an oracle for A, and an oracle for an NP-complete problem (the oracles are used separately, not nested in any way), you can solve a PSPACE-complete problem in polynomial time.

A related question is there, but it is not answered.

  • $\begingroup$ What is an “NP reduction”? $\endgroup$ Feb 11 at 9:47
  • $\begingroup$ @EmilJeřábek I added a more precise description, it's true that different definitions could be considered $\endgroup$
    – Denis
    Feb 11 at 10:12
  • $\begingroup$ @Denis - isn't it the same as asking whether there is a problem $A$ such that $A$ is not known to be PSPACE-hard, but $PSPACE\subseteq (P^{NP})^A$? If so, it seems that such a problem would either make the polynomial hierarchy collapse, or separate PH from PSPACE. $\endgroup$
    – Shaull
    Feb 11 at 11:34
  • 1
    $\begingroup$ @Denis - Right. I meant if we had such a problem that is provably not PSPACE-complete, but that's pointless, as you mention. By the way, have you looked at this? Maybe the intermediate problems can be used as a candidate: cstheory.stackexchange.com/questions/7639/… $\endgroup$
    – Shaull
    Feb 11 at 13:23
  • 1
    $\begingroup$ Thanks @Shaull, the question came from an automaton problem, where it was easier to find the NP reduction than the P one, so I was wondering whether it has happened that for some problem we stayed in the first stage. $\endgroup$
    – Denis
    Feb 11 at 13:56

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.