3
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ What is an “NP reduction”? $\endgroup$
    – Emil Jeřábek
    Commented Feb 11, 2021 at 9:47
  • $\begingroup$ @EmilJeřábek I added a more precise description, it's true that different definitions could be considered $\endgroup$
    – Denis
    Commented Feb 11, 2021 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
    Commented Feb 11, 2021 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
    Commented Feb 11, 2021 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
    Commented Feb 11, 2021 at 13:56

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.