<p>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 ?</p>
<p>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.</p>
<p>A related question is <a href="https://cstheory.stackexchange.com/questions/31797/pspace-completeness-with-different-kinds-of-reductions">there</a>, but it is not answered.</p>

CC BY-SA 4.0
2021-02-11T09:47:32.227Z
What is an “NP reduction”?
Emil Jeřábek
CC BY-SA 4.0
2021-02-11T10:12:53.177Z
@EmilJeřábek I added a more precise description, it's true that different definitions could be considered
Denis
CC BY-SA 4.0
2021-02-11T11:34:52.460Z
@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
CC BY-SA 4.0
2021-02-11T13:16:51.000Z
@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
CC BY-SA 4.0
2021-02-11T13:23:41.093Z
@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
CC BY-SA 4.0
2021-02-11T13:56:03.887Z
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
CC BY-SA 4.0
2021-02-11T16:43:44.360Z
@Denis - well, as we all know, *every* interesting problem comes from automata :)
Shaull
<cc.complexity-theory><pspace>
PSPACE-complete under NP reduction
Denis
# PSPACE-complete under NP reduction

(Asked by: username_0 on 2021-02-11)

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](https://cstheory.stackexchange.com/questions/31797/pspace-completeness-with-different-kinds-of-reductions), but it is not answered.

**Tags:** cc.complexity-theory, pspace

> **Comments:**
> **username_1**: What is an “NP reduction”?  
> **username_0**: @EmilJeřábek I added a more precise description, it's true that different definitions could be considered  
> **username_2**: @username_0 - 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.  
> **username_0**: @username_2 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.  
> **username_2**: @username_0 - 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  
> **username_0**: Thanks @username_2, 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.  
> **username_2**: @username_0 - well, as we all know, *every* interesting problem comes from automata :)  

---

## 0 answers

