# PSPACE-complete under NP reduction

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.

• What is an “NP reduction”? Feb 11 at 9:47
• @EmilJeřábek I added a more precise description, it's true that different definitions could be considered Feb 11 at 10:12
• @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. Feb 11 at 11:34
• @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/… Feb 11 at 13:23
• 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. Feb 11 at 13:56