2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Which step aren't you sure of? Do you understand what you are trying to prove? Do you understand what the time hierarchy theorem is saying? Have you seen a proof? $\endgroup$ – Yuval Filmus Mar 16 '13 at 14:48
  • $\begingroup$ Just solving the question using mindless manipulation isn't helpful at all. Try to understand what you're doing and why. Why is this question interesting at all? Why do we care if E=EXP or not? $\endgroup$ – Yuval Filmus Mar 16 '13 at 14:49
  • $\begingroup$ @YuvalFilmus i don't understand your answer. I care because it is a given problem to me which i am trying to solve. If i would understand everything, i guess i wouldn't be here asking, right ? I am asking if the proof is correct, if not how should it be done. $\endgroup$ – Devid Mar 16 '13 at 15:52
  • $\begingroup$ Are you sure you're allowed to use the THT as such? What kind of class are you attending? The way you present it, this exercise seems quite pointless. $\endgroup$ – frafl Mar 16 '13 at 17:12
  • 1
    $\begingroup$ No, I meant that you did not pick $n^c$, but a function that grows faster than $n^c$ for all $c$, now find a function that grows faster than $2^{cn}$ for all $c$. $\endgroup$ – frafl Mar 16 '13 at 20:49
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Just below the \frac, I think you have $g$and $f$ swapped. $\endgroup$ – Luke Mathieson Mar 17 '13 at 3:12
2
$\begingroup$

While the answer of Yuval Filmus is absolutely correct, the comments and the correct proof for P in the question indicate that the problem of the OP is finding the intermediate class $\mathcal{C}$ between $\mathsf{E}$ and $\mathsf{EXP}$ ($\mathsf{E} \subseteq \mathcal{C}\subsetneq \mathsf{EXP}$).

As Yuval Filmu also indicates ("you want to find a single language $\dots$") you actually don't need to explicitly construct such a class if you use the proof of the theorem and not the theorem itself, as all you need is the diagonal language of this class, which will work as a counterexample for all subclasses (like $\mathsf{E}$) too.

This diagonal language is for the class $\mathsf{DTIME}(f)$

$$D_f = \{ (w, x) \mid M_w \text{ accepts } x \text{ in } f(|x|) \text{ steps} \}\quad.$$

Of course it does not work for $\mathsf{DTIME}(\mathcal{O}(f))$ (let alone $\mathsf{DTIME}(2^{\mathcal{O}(f)})$):

$$D_{\mathcal{O}(f)} = \{ (w, x) \mid M_w \text{ accepts } x \text{ in } \mathcal{O}(f(|x|)) \text{ steps} \}\quad.$$

How shall the poor Turing Machine know which $f$ is relevant while deciding $D_{\mathcal{O}(f)}$?

So instead of $\mathcal{F}=\mathcal{O}(f)$ (or generally any class of functions $\mathcal{F}$) you need a $g$ that grows at least as fast as any function in $\mathcal{F}$. In most cases you need a function that grows faster than any $f\in \mathcal{F}$, because if it grows as fast as a function in $\mathcal{F}$, you'll find a function in $\mathcal{F}$ that grows faster than $g$.

As stated in the question $g(n)=2^n$ is a good choice for $\mathsf{P}$, if you want to show its relation to $\mathsf{EXP}$, for $\mathsf{E}$ $g(n)=2^{n^k}$ for any $k>1$ will do the trick.


Resumé of the possible "proofs":

  1. $\mathsf{E}=\mathsf{DTIME}(2^{\mathcal{O}(n)}) \subsetneq \mathsf{EXP}$ via THT (does not work)
  2. $\mathsf{E}\subseteq\mathsf{DTIME}(2^{n^{k}}) \subsetneq \mathsf{EXP}$ via THT (works if $k>1$)
  3. $D_f \in \mathsf{EXP}\setminus\mathsf{E}$, where $f(n)=2^{n^{k}}$ (works analogously to a proof for the THT if $k>1$)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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