<blockquote>
  <ol start="2">
  <li>Query the oracle to solve $K$. Since we've assumed that $PSPACE = EXPTIME$, the answer must therefore fit in polynomial space; so it
  will only take polynomial time to write the answer to the tape.</li>
  </ol>
</blockquote>

<p>You are talking about decision problems. They only have yes and no answers, which you can write down quickly regardless of relationships between complexity classes.</p>

<blockquote>
  <p>Both steps together still take polynomial time, so $EXPTIME^K = P^K$.</p>
</blockquote>

<p>No. You first promise to solve $EXPTIME$ problems and now claiming to solve $EXPTIME^K$. The proper conclusion is:</p>

<p>$$EXPTIME = P^K$$</p>

<p>Which is true, by definition of $EXPTIME$-completeness.</p>

CC BY-SA 4.0
2018-08-28T10:39:59.950Z
But the $K$ oracle does not change $EXPTIME$. SO $EXPTIME^K = EXPTIME$
user2894959
CC BY-SA 4.0
2018-08-28T11:12:46.273Z
@user2894959 you seem to misunderstand what being an oracle means. Oracles always answer within single computation step, while $EXPTIME$-complete problems require exponentional time.
Dmitri Urbanowicz
CC BY-SA 4.0
2018-08-28T11:45:57.977Z
https://cs.stackexchange.com/a/81219/90072 should help to clarify, why you’d get a different complexity class.
Dmitri Urbanowicz
CC BY-SA 4.0
2018-08-28T13:57:43.493Z
Also note that if it were the case that $\mathrm{EXPTIME}^K=\mathrm{EXPTIME}$, you’d immediately get $\mathrm P^K=\mathrm{EXPTIME}^K$ contradicting the time hierarchy theorem, without using any assumptions involving PSPACE.
Emil Jeřábek
CC BY-SA 4.0
2018-08-28T09:21:14.070Z
2018-08-28T09:21:14.070Z
Dmitri Urbanowicz
<p>It seems obvious to me that $PSPACE \neq EXPTIME$. I, however, do not believe that my seemingly obvious logic would not be picked up by more intelligent people if it was so simple, so I'm assuming there is some kind of a false assumption I'm making.</p>

<p>We know that there are $EXPTIME$-complete problems; i.e. any problem in $EXPTIME$ has a polynomial-time reduction to some problem $K$. So here's my take on this:</p>

<p>Assume we have an oracle for $K$. Now assume that $PSPACE = EXPTIME$. That means there must be <em>some</em> algorithm in $PSPACE$ which solves $K$. But now note, that with an oracle for $K$, we could solve any $EXPTIME$ problem as follows:</p>

<ol>
<li>Reduce the problem to $K$, which takes polynomial time.</li>
<li>Query the oracle to solve $K$. Since we've assumed that $PSPACE = EXPTIME$, the answer must therefore fit in polynomial space; so it will only take polynomial time to write the answer to the tape.</li>
</ol>

<p>Both steps together still take polynomial time, so $EXPTIME^K = P^K$. However, we know by the time hierarchy theorem, which relativizes, there cannot be an oracle such that $P^X = EXPTIME^X$, so our original assumption that $PSPACE = EXPTIME$ is wrong. Therefore, $PSPACE \neq EXPTIME$.</p>

<p>Where's the error in my reasoning?</p>

CC BY-SA 4.0
2018-08-28T00:16:47.200Z
Assume problem $Q$ is in $EXPTIME^K$.  This means there is a way to solve $Q$ in exponential time on a Turing machine that has access to $K$.  It's not clear to me why $EXPTIME=PSPACE$ would have any implications for that Turing machine.   (The fact that $Q \in EXPTIME^K$ doesn't imply that $Q \in EXPTIME$; and I don't see any guarantee that there is a problem $R \in EXPTIME$ such that this computation is solving $R$.  It's not clear what it would mean to run this Turing machine without an oracle, so it's not clear how to apply $EXPTIME=PSPACE$ to conclude anything about that Turing machine.)
D.W.
<cc.complexity-theory><exp-time-algorithms><pspace>
Why is it a mystery if PSPACE ?= EXPTIME?
user2894959
# Why is it a mystery if PSPACE ?= EXPTIME?

(Asked by: username_0 on 2018-08-27)

It seems obvious to me that $PSPACE \neq EXPTIME$. I, however, do not believe that my seemingly obvious logic would not be picked up by more intelligent people if it was so simple, so I'm assuming there is some kind of a false assumption I'm making.

We know that there are $EXPTIME$-complete problems; i.e. any problem in $EXPTIME$ has a polynomial-time reduction to some problem $K$. So here's my take on this:

Assume we have an oracle for $K$. Now assume that $PSPACE = EXPTIME$. That means there must be *some* algorithm in $PSPACE$ which solves $K$. But now note, that with an oracle for $K$, we could solve any $EXPTIME$ problem as follows:

1. Reduce the problem to $K$, which takes polynomial time.
2. Query the oracle to solve $K$. Since we've assumed that $PSPACE = EXPTIME$, the answer must therefore fit in polynomial space; so it will only take polynomial time to write the answer to the tape.

Both steps together still take polynomial time, so $EXPTIME^K = P^K$. However, we know by the time hierarchy theorem, which relativizes, there cannot be an oracle such that $P^X = EXPTIME^X$, so our original assumption that $PSPACE = EXPTIME$ is wrong. Therefore, $PSPACE \neq EXPTIME$.

Where's the error in my reasoning?

**Tags:** cc.complexity-theory, exp-time-algorithms, pspace
> **Comments:**
> **username_1**: Assume problem $Q$ is in $EXPTIME^K$.  This means there is a way to solve $Q$ in exponential time on a Turing machine that has access to $K$.  It's not clear to me why $EXPTIME=PSPACE$ would have any implications for that Turing machine.   (The fact that $Q \in EXPTIME^K$ doesn't imply that $Q \in EXPTIME$; and I don't see any guarantee that there is a problem $R \in EXPTIME$ such that this computation is solving $R$.  It's not clear what it would mean to run this Turing machine without an oracle, so it's not clear how to apply $EXPTIME=PSPACE$ to conclude anything about that Turing machine.)  

---

## 1 answers

### Answer by username_2 on 2018-08-28. Score: 2

> 2. Query the oracle to solve $K$. Since we've assumed that $PSPACE = EXPTIME$, the answer must therefore fit in polynomial space; so it
>    will only take polynomial time to write the answer to the tape.

You are talking about decision problems. They only have yes and no answers, which you can write down quickly regardless of relationships between complexity classes.

> Both steps together still take polynomial time, so $EXPTIME^K = P^K$.

No. You first promise to solve $EXPTIME$ problems and now claiming to solve $EXPTIME^K$. The proper conclusion is:

$$EXPTIME = P^K$$

Which is true, by definition of $EXPTIME$-completeness.

> **Comments:**
> **username_0**: But the $K$ oracle does not change $EXPTIME$. SO $EXPTIME^K = EXPTIME$  
> **username_2**: @user2894959 you seem to misunderstand what being an oracle means. Oracles always answer within single computation step, while $EXPTIME$-complete problems require exponentional time.  
> **username_2**: https://cs.stackexchange.com/a/81219/90072 should help to clarify, why you’d get a different complexity class.  
> **username_3**: Also note that if it were the case that $\mathrm{EXPTIME}^K=\mathrm{EXPTIME}$, you’d immediately get $\mathrm P^K=\mathrm{EXPTIME}^K$ contradicting the time hierarchy theorem, without using any assumptions involving PSPACE.  

---

