-2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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.) $\endgroup$
    – D.W.
    Aug 28, 2018 at 0:16

1 Answer 1

Reset to default
2
$\begingroup$
  1. 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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ But the $K$ oracle does not change $EXPTIME$. SO $EXPTIME^K = EXPTIME$ $\endgroup$
    – user2894959
    Aug 28, 2018 at 10:39
  • 1
    $\begingroup$ @user2894959 you seem to misunderstand what being an oracle means. Oracles always answer within single computation step, while $EXPTIME$-complete problems require exponentional time. $\endgroup$
    – Dmitri Urbanowicz
    Aug 28, 2018 at 11:12
  • 2
    $\begingroup$ cs.stackexchange.com/a/81219/90072 should help to clarify, why you’d get a different complexity class. $\endgroup$
    – Dmitri Urbanowicz
    Aug 28, 2018 at 11:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Aug 28, 2018 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.