-2
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ What did you try? Have you tried expanding the definitions? $\endgroup$
    – Pål GD
    Jul 3, 2018 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, 2018 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, 2018 at 0:45
  • 1
    $\begingroup$ cs.stackexchange.com/questions/6649/… $\endgroup$
    – xskxzr
    Jul 5, 2018 at 11:27

1 Answer 1

3
$\begingroup$

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

$\endgroup$
3
  • $\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, 2018 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$ Jul 4, 2018 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, 2018 at 12:12

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