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


closed as unclear what you're asking by Pål GD, Evil, Discrete lizard, David Richerby, vonbrand Jul 6 '18 at 15:16

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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$?

  • $\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.