How to prove that "EXPtime contains PSPACE"?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ What did you try? Have you tried expanding the definitions? $\endgroup$– John KemenyCommented 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$– smallCommented 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 NCommented Jul 5, 2018 at 0:45
-
1$\begingroup$ cs.stackexchange.com/questions/6649/… $\endgroup$– xskxzrCommented Jul 5, 2018 at 11:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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$– smallCommented 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$ Commented 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$– smallCommented Jul 7, 2018 at 12:12