[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:

• $E\subseteq 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 $P\subsetneq EXP$:
PROOF IDEA:

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

---

Complexity class E: $E=\bigcup_{c\ge 0}TIME(2^{cn})$
Complexity Class EXPTIME: $EXP=\bigcup_{c\ge 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