3

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.

Denis
  • 8,843
  • 28
  • 55
  • What is an “NP reduction”? – Emil Jeřábek Feb 11 '21 at 09:47
  • @EmilJeřábek I added a more precise description, it's true that different definitions could be considered – Denis Feb 11 '21 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. – Shaull Feb 11 '21 at 11:34
  • @Shaull How could it be that not having found a proof yet for PSPACE-hardness of $A$ could yield any collapsing or separation result ? You probably mean this happens if we have a proof that $A$ is not PSPACE-hard. – Denis Feb 11 '21 at 13:16
  • 1
    @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: https://cstheory.stackexchange.com/questions/7639/is-there-a-pspace-intermediate-language/7640#7640 – Shaull Feb 11 '21 at 13:23
  • 1
    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. – Denis Feb 11 '21 at 13:56
  • @Denis - well, as we all know, every interesting problem comes from automata :) – Shaull Feb 11 '21 at 16:43

0 Answers0