Chapter 9: Q2E (page 389)

Prove that $TIME (2^{n}) ⊈ TIME ({2^{2}}^{n})$

Short Answer

Expert verified

The above problem can be solved using Turing Machine, and the time hierarchy theorem which shows that the function $2 n$ is time constructible.

Step by step solution

Using the Time Hierarchy Theorem

The $TIME (2^{n}) \subseteq TIME ({2^{2}}^{n})$ holds because $2^{n} \leq 2^{2 n}$ .

According to the time Hierarchy theorem, if $f (n) \log f (n) = O (g (n))$ and f, g are time-constructible functions then, $D TIME (f (n)) ⊈ D TIME (g (n))$

Thus, as discussed in time-hierarchy theorem the above containment

$TIME (2^{n}) \subseteq TIME ({2^{2}}^{n})$ is proper

Using Turing Machine to prove the problem

As we can write the number 1 followed by $2 n$ 0s in $O (2^{2 n})$ time by making the function $2^{2 n}$ time constructible

Hence by the guarantees of the Time Hierarchy theorem, it can be decided whether a language A exists in $O (2^{2 n})$ time but not in $o (\frac{2^{2 n}}{\log 2^{2 n}}) = o (\frac{2^{2 n}}{2 n})$

time.

So, $A \in TIME ({2^{2}}^{n})$ but $A \notin TIME (2^{n})$

Hence, we can say that. $TIME (2^{n}) ⊈ TIME ({2^{2}}^{n})$

Unlock Step-by-Step Solutions & Ace Your Exams!

Full Textbook Solutions
Get detailed explanations and key concepts
Unlimited Al creation
Al flashcards, explanations, exams and more...
Ads-free access
To over 500 millions flashcards
Money-back guarantee
We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

Recommended explanations on Computer Science Textbooks

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Prove that $TIME (2^{n}) ⊈ TIME ({2^{2}}^{n})$

Short Answer

Step by step solution

Using the Time Hierarchy Theorem

Using Turing Machine to prove the problem

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Computer Science Textbooks

Computer Systems

Computer Programming

Problem Solving Techniques

Databases

Functional Programming

Data Structures

Study anywhere. Anytime. Across all devices.

Prove that TIME(2n)⊈TIME(22n)

Short Answer

Step by step solution

Using the Time Hierarchy Theorem

Using Turing Machine to prove the problem

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Computer Science Textbooks

Computer Systems

Computer Programming

Problem Solving Techniques

Databases

Functional Programming

Data Structures

Study anywhere. Anytime. Across all devices.

Prove that $TIME (2^{n}) ⊈ TIME ({2^{2}}^{n})$