How to prove that "EXPtime contains PSPACE"?enter image description here

  • 1
    $\begingroup$ What did you try? Have you tried expanding the definitions? $\endgroup$ – Pål GD Jul 3 '18 at 21:55
  • $\begingroup$ Because i live in bad country, I can't prove it , I tried to use the definitions of pspace , I manged to prove that p is contained in pspace but I could not find the Relationship between exptime and pspace $\endgroup$ – small Jul 4 '18 at 11:50
  • $\begingroup$ Here's a generalization of your problem, whose proof might end up being simpler to derive a first time. Prove that for any computable function $f(n)$ satisfying $f(n) = \Omega(n)$, $\mathrm{SPACE}[f(n)] \subseteq \mathrm{DTIME}[2^{O(f(n))}]$. Your sought statement follows by noting that this implies $\mathrm{PSPACE} = \bigcup_{i \in \mathbb{N}} \mathrm{SPACE}[n^i] \subseteq \bigcup_{i \in \mathbb{N}} \mathrm{DTIME}[2^{O(n^i)}] = \mathrm{EXPTIME}.$ $\endgroup$ – Yonatan N Jul 5 '18 at 0:45
  • 1
    $\begingroup$ cs.stackexchange.com/questions/6649/… $\endgroup$ – xskxzr Jul 5 '18 at 11:27

Well, because this looks really like a homework question I give you the following hint:

What is PSAPCE exactly? How is "time" measured in sense of a turing computation? With these prerequesites, why is any problem, which is in PSPACE, "by definition" in EXPTIME?

Hope, I could give you some sketch

Edit (more hints): Okay, you have to be a bit more precise with your definitions: PSPACE is a set whereby, for all $A \in PSPACE$ there exists a Turing-Machine $M$, that can compute on an input $x$ with length $n$, if $x$ is a solution of the problem $A$ with at most using polynomial space on the turing working tape: Formal: Let $x$ be the input (length $n$) of $M$, and $f(x)$ shows the number of cells which are used (that means, the read/write head of $M$ visits this cell at least once) during the computation.
Then, there is $f \in \mathcal{O}(n^k)$ for one $k \in \mathbb{N}$ iff. $A \in PSPACE$

Now your exercise: What is the difference from EXPTIME in this definition? And why would any input (possible solution) $x$ (and its computation!) of a Problem $A \in PSPACE$ satisfy the proposition of $A \in EXPTIME$?

| cite | improve this answer | |
  • $\begingroup$ Thank you for your interest but; I live in a backward country so this is really not a homework. I study the computational complexity without a teacher The PSPACE is a GROUP of all languages that solve a Poly Space but I can not find any way to prove that time is EXP , I hipe that you will help me $\endgroup$ – small Jul 4 '18 at 11:33
  • 1
    $\begingroup$ @small I have extended my answer for you and you're welcome to ask further questions, if I see that you have made your own thoughts. And btw sorry for my bad English. $\endgroup$ – Panzerkroete Jul 4 '18 at 23:23
  • $\begingroup$ I am very grateful to you I was able to prove this, and i understand the reason. thanks to God then to you because you help me I hope you stay by my side so that I can continue my studies $\endgroup$ – small Jul 7 '18 at 12:12

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