[Solved]: How to Prove E $subsetneq$ EXP?

Problem Detail: I want to prove that $E subsetneq EXP$ and i would like to do so using the Time Hierarchy Theorem I need to choose $f(n)$, i think $2^{cn}$ is a good choice, so here is my Proof:

  • $Esubseteq TIME(2^{cn})$
  • $TIME(2^{cn}) subsetneq TIME(n^2 cdot (2^{cn})^2)$ Time Hierarchy Theorem
  • $E subsetneq EXP$

Is this correct ? I have done something similar with $Psubsetneq EXP$:
PROOF IDEA:

  • $Psubseteq TIME(2^n)$
  • $TIME(2^n)subsetneq TIME(n^2cdot (2^n)^2) text{Time Hierarchy Theorem}$
  • $TIME(n^2cdot (2^n)^2)subseteq EXP$
  • $Psubsetneq EXP$

Complexity class E: $E=bigcup_{cge 0}TIME(2^{cn})$
Complexity Class EXPTIME: $EXP=bigcup_{cge 0}TIME(2^{n^c})$
Time Hierarchy Theorem: $TIME(f(n)) subsetneq TIME(n²cdot (fn)²)$

The Time Hierarchy Theorem shows that allowing Turing Machines more computation time strictly increases the class of languages that they can decide. Recall that a function $f : N → N$ is a time-constructible function if there is a Turing machine that, given the input $1^n$ , writes down $1^{f(n)}$ on its tape in $O(f (n))$ time.

Asked By : Devid

Answered By : Yuval Filmus

The time hierarchy theorem states that if $f(n)$ is a reasonable function (technically, time-constructible), then there are some languages computable in time $f(n)$ that require (almost) time $f(n)$. More accurately, for any $g(n)$ satisfying $$ frac{g(n)log f(n)}{f(n)} longrightarrow 0, $$ there is a function computable in time $f(n)$ but not in time $g(n)$. Intuitively, this is saying that if we have more time ($f(n)$ rather than $g(n)$), then we can compute more languages. The theorem is a time-bounded version of the undecidability of the halting problem, and is proved in a very similar way. In your case, you want to show that time $O(2^{n^gamma})$ is more powerful than time $O(2^{cn})$. Here is one naive attempt: pick some $f(n) in O(2^{n^gamma})$ such that for all $g(n) in O(2^{cn})$, the prerequisites of the time hierarchy theorem are satisfied. This shows that for each particular $c$, there is a language in EXP not computable in time $O(2^{cn})$. However, for all we know it can be computed in time $O(2^{(c+1)n})$, and so this doesn’t show that EXP is larger than E. Instead, you want to find a single language in EXP which is simultaneously not computable in time $O(2^{cn})$ for all $c$. To ensure that, you need to pick $g(n)$ judiciously, and I’ll leave you to that.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10551  Ask a Question  Download Related Notes/Documents