0
$\begingroup$

It's impossible for a problem to require exponential space without being exponential-time.

  1. Consider that if an $EXPSPACE~~complete$ problem can be solved in $2^n$ time. It will now fall into the class $EXPTIME$.
  2. Then $EXPSPACE~~complete$ problems are in $EXP$ if they can be solved in $2^n$ time. This means they can reduce into $EXP~~complete$ problems and vice versa.

To me, this should be easy to write a proof that $EXPTIME$ = $EXPSPACE$.

My intuition tells me that if $Exptime$ = $Expspace$; then $PSPACE$ != $EXPTIME$,

Because $PSPACE$ already is not equal to $EXPSPACE$.

Question

As an amateur, what would make this reasoning be wrong or right?

$\endgroup$
2
$\begingroup$

I did not understand the first part of the question, but just so you know, its unknown whether $EXPTIME=EXPSPACE$ or not. What is known is that $EXPSPACE\subseteq \bigcup _cDTIME(2^{2^{n^c}})$ from the relations shown here.

The second part of the question: If $EXPTIME=EXPSPACE$ then $PSPACE\neq EXPTIME$, is absolutely correct: by the space hierarchy theorem, $PSPACE\subsetneq EXPSPACE$ and therefore $PSPACE\subsetneq EXPTIME$ as $EXPSPACE=EXPTIME$ (by our assumption).

$\endgroup$

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.