Proof of the Time Hierarchy Theorem

Author

Your Name

Published

January 28, 2025

Introduction

This document presents a detailed proof of the Time Hierarchy Theorem, a fundamental result in complexity theory. This theorem establishes a strict hierarchy within time complexity classes, demonstrating that increasing the time bound allows us to solve strictly more problems. Specifically, the theorem states that for any proper time complexity function $F$, where $F(n) \geq n$, the complexity class $\text{TIME}(F(n))$ is strictly contained within $\text{TIME}(F(n)^3)$.

The proof relies on the construction and analysis of a specific language, denoted as $h_F$. This language is carefully designed to serve as a witness to the separation between the complexity classes. The proof is structured around two key lemmas:

Lemma 3: Demonstrates that the language $h_F$ belongs to the complexity class $\text{TIME}(F(n)^3)$.
Lemma 4: Demonstrates that the language $h_F$ does not belong to the complexity class $\text{TIME}(F(\lfloor n/2 \rfloor))$.

By proving these two lemmas, we establish that $h_F$ is a language that can be decided in $\mathcal{O}(F(n)^3)$ time but not in $\mathcal{O}(F(\lfloor n/2 \rfloor))$ time, thus proving the strict inclusion of $\text{TIME}(F(n))$ in $\text{TIME}(F(n)^3)$. This separation is achieved through a diagonalization argument, a common technique for proving lower bounds in complexity theory.

The subsequent sections will provide the necessary definitions, detailed proofs of the two lemmas, and a concluding discussion. The proof also includes a crucial correction factor, $F'(n) = F(n) + 5n + 4$, in the definition of $h_F$, which is essential for the correctness of the argument.

Preliminaries

This section introduces the essential definitions and notations required for the proof of the Time Hierarchy Theorem. These definitions lay the groundwork for the subsequent lemmas and the final theorem.

A function $F: \mathbb{N} \to \mathbb{N}$ is considered proper if it satisfies the following conditions:

$F$ is non-decreasing, i.e., $F(n) \leq F(n+1)$ for all $n \in \mathbb{N}$.
There exists a Turing machine $M_F$ that, given an input $n$ (represented in unary as a string of $n$ ones), computes $F(n)$ in unary within $\mathcal{O}(F(n))$ time.

Significance: Proper functions are essential because they represent realistic time complexity bounds that can be computed efficiently by a Turing machine. This property is crucial for the simulation arguments used in the proof.

Let $F$ be a proper function. The language $h_F$ is defined as the set of strings $mx$ such that the Turing machine $M$, when given input $x$, accepts within at most $F'(|x|)$ steps. Here, $F'(n)$ is defined as: \[F'(n) = F(n) + 5n + 4\] where $|x|$ denotes the length of the string $x$. Purpose: The language $h_F$ is specifically constructed to serve as a witness for the separation of time complexity classes. It is designed such that it can be decided in $\mathcal{O}(F(n)^3)$ time but not in $\mathcal{O}(F(\lfloor n/2 \rfloor))$ time.

The function $F'(n) = F(n) + 5n + 4$ is a crucial component of the definition of $h_F$. The additional $5n+4$ term is a technical correction necessary for the diagonalization argument in Lemma 4 to work correctly. This correction ensures that the simulation of Turing machines within the proof can be accurately analyzed and avoids a potential contradiction. Without this correction, the diagonalization argument would fail.

Lemma 1: $h_F \in \text{TIME}(F(n)^3)$

Lemma 1: If $F$ is a proper function such that $F(n) \geq n$, then the language $h_F$ belongs to the complexity class $\text{TIME}(F(n)^3)$.

Proof. Proof. To prove this lemma, we will construct a universal Turing machine $U_F$ that decides the language $h_F$ within $\mathcal{O}(F(n)^3)$ time. This machine will simulate any given Turing machine $M$ on input $x$ for a limited number of steps determined by $F'(|x|)$.

Construction of $U_F$

The universal Turing machine $U_F$ takes as input a string of the form $\langle M, x \rangle$, where $M$ is the encoding of a Turing machine and $x$ is an input string for $M$. Let $n = |M| + |x|$ denote the total length of the input. The machine $U_F$ operates as follows:

Compute $F'(|x|)$: $U_F$ computes $F'(|x|) = F(|x|) + 5|x| + 4$ in unary on a dedicated working tape. Since $F$ is a proper function, $F'$ is also proper. Let $M_{F'}$ be a Turing machine that computes $F'(n)$ in unary in $\mathcal{O}(F'(n))$ time. $U_F$ simulates $M_{F'}$ on input $|x|$ to obtain $F'(|x|)$ in unary. This step takes $\mathcal{O}(F'(|x|)) = \mathcal{O}(F(|x|))$ time. Since $|x| \leq n$, this step is bounded by $\mathcal{O}(F(n))$.
Store initial configuration: $U_F$ stores the initial configuration of $M$ on input $x$ on another working tape, referred to as the configuration tape. This configuration includes the initial state of $M$, the initial head positions, and the content of all tapes of $M$. Initially, the first tape contains the input $x$, and all other tapes are blank. This step involves copying $x$ and adding a constant amount of information, taking $\mathcal{O}(n)$ time.
Simulate $M$: $U_F$ simulates the execution of $M$ on $x$ step by step. For each step of $M$, $U_F$ performs the following:
1. Update configuration: $U_F$ scans the configuration tape to determine the current state of $M$ and the symbols under the read heads. This takes time proportional to the length of the configuration tape.
2. Find transition rule: $U_F$ scans the encoding of $M$ (part of the input) to find the transition rule that corresponds to the current state and the symbols read.
3. Apply transition: $U_F$ applies the transition rule, updating the configuration tape to reflect the new state, head positions, and tape contents. This may involve shifting parts of the tape, which takes time proportional to the length of the configuration tape.
After each step of $M$ is simulated, $U_F$ deletes one symbol from the tape containing $F'(|x|)$.
Termination: $U_F$ terminates with "yes" if $M$ reaches an accepting state before all symbols in $F'(|x|)$ are deleted. If all symbols in $F'(|x|)$ are deleted before $M$ reaches an accepting state, $U_F$ terminates with "no".

Time Complexity Analysis

Now, let’s analyze the time complexity of each step:

Step 1: Computing $F'(|x|)$ takes $\mathcal{O}(F(n))$ time, as $F$ is a proper function.
Step 2: Storing the initial configuration takes $\mathcal{O}(n)$ time, as it involves copying the input $x$ and a constant amount of additional information.
Step 3: Updating the configuration:
- Let $k$ be the number of tapes of $M$. The length of the configuration tape is at most $k \cdot F'(|x|)$, which is $\mathcal{O}(k \cdot F(|x|))$. Since $k$ is bounded by the length of the encoding of $M$, which is part of the input, we have $k \leq |M| \leq n$. Also, $|x| \leq n$. Thus, the length of the configuration tape is at most $\mathcal{O}(n \cdot F(n))$. Since $F(n) \geq n$, the length of the configuration tape is $\mathcal{O}(F(n)^2)$.
- Each update of the configuration involves scanning and modifying the configuration tape, which takes time proportional to the length of the configuration tape, i.e., $\mathcal{O}(F(n)^2)$.
Step 3: The number of updates is at most $F'(|x|)$, which is $\mathcal{O}(F(|x|)) = \mathcal{O}(F(n))$. This is because $U_F$ simulates $M$ for at most $F'(|x|)$ steps.

Therefore, the total time complexity of $U_F$ is: \[\mathcal{O}(F(n)) + \mathcal{O}(n) + \mathcal{O}(F(n)) \cdot \mathcal{O}(F(n)^2) = \mathcal{O}(F(n)^3)\] Thus, we conclude that $h_F \in \text{TIME}(F(n)^3)$. ◻

Lemma 2: $h_F \notin \text{TIME}(F(\lfloor n/2 \rfloor))$

Lemma 2: If $F$ is a proper function such that $F(n) \geq n$, then the language $h_F$ does not belong to the complexity class $\text{TIME}(F(\lfloor n/2 \rfloor))$.

Proof. Proof. We will prove this lemma by contradiction using a diagonalization argument. Assume that there exists a Turing machine $M_{h_F}$ that decides the language $h_F$ in at most $F(\lfloor n/2 \rfloor)$ steps, where $n$ is the length of the input. This assumption will lead to a contradiction, proving that such a machine cannot exist.

Construction of a Diagonalizing Machine $D$

We define a Turing machine $D$ that takes as input the encoding of a Turing machine $M$ and operates as follows:

Construct input: $D$ constructs the input $\langle M, M \rangle$, which is the encoding of the pair consisting of the machine $M$ and the input $M$ (i.e., $M$ is given its own encoding as input). This step involves copying the input $M$.
Simulate $M_{h_F}$: $D$ simulates the execution of $M_{h_F}$ on the input $\langle M, M \rangle$.
Diagonalize: If $M_{h_F}$ accepts $\langle M, M \rangle$, then $D$ rejects. If $M_{h_F}$ rejects $\langle M, M \rangle$, then $D$ accepts. In essence, $D$ does the opposite of what $M_{h_F}$ does on the input $\langle M, M \rangle$.

Thus, $D(M)$ accepts if and only if $M_{h_F}(M, M)$ rejects. This diagonalization step is crucial for creating a contradiction.

Analysis of $D$

The behavior of $D$ is defined such that $D(M)$ accepts if and only if $M_{h_F}(M, M)$ rejects, which means that $\langle M, M \rangle \notin h_F$. This implies one of the following:

$M$ on input $M$ rejects.
$M$ on input $M$ accepts after more than $F'(|M|) = F(|M|) + 5|M| + 4$ steps.
$M$ on input $M$ does not halt.

These conditions are a direct consequence of the definition of the language $h_F$.

Contradiction

Now, let’s consider the behavior of $D$ when given its own encoding as input, i.e., $D(D)$. This is the core of the diagonalization argument.

Case 1: $D(D)$ accepts. If $D(D)$ accepts, then by the definition of $D$, it means that $M_{h_F}(D, D)$ rejects. This implies that $\langle D, D \rangle \notin h_F$. However, if $\langle D, D \rangle \notin h_F$, then $D(D)$ must either reject or run for more than $F'(|D|)$ steps, which contradicts our assumption that $D(D)$ accepts.
Case 2: $D(D)$ rejects. If $D(D)$ rejects, then by the definition of $D$, it means that $M_{h_F}(D, D)$ accepts. This implies that $\langle D, D \rangle \in h_F$. However, if $\langle D, D \rangle \in h_F$, then $D(D)$ must accept within $F'(|D|)$ steps, which contradicts our assumption that $D(D)$ rejects.

In both cases, we reach a contradiction, demonstrating that our initial assumption about the existence of $M_{h_F}$ must be false.

Time Complexity of $D$

Let $n = |M|$ be the length of the input $M$.

Constructing $\langle M, M \rangle$: This step involves copying the string $M$, which takes $2n + 1$ steps (including a separator). Thus, this step takes $\mathcal{O}(n)$ time.
Simulating $M_{h_F}$: Simulating $M_{h_F}$ on $\langle M, M \rangle$ takes at most $F(\lfloor (2n+1)/2 \rfloor)$ steps, which is bounded by $F(n)$ steps.

Therefore, the total time complexity of $D$ is $\mathcal{O}(n) + F(\lfloor (2n+1)/2 \rfloor) = \mathcal{O}(F(n))$. More precisely, the time complexity of $D$ is $F(n) + 5n + 4$. This is the crucial point where the correction factor $5n+4$ is used.

If $D(D)$ accepts, it must do so in at most $F(|D|) + 5|D| + 4$ steps. However, if $D(D)$ accepts, it means that $M_{h_F}(D, D)$ rejects, so $\langle D, D \rangle \notin h_F$. This implies that $D(D)$ either rejects or runs for more than $F'(|D|)$ steps. This contradicts the assumption that $D(D)$ accepts in at most $F(|D|) + 5|D| + 4$ steps.

Therefore, our initial assumption that there exists a machine $M_{h_F}$ that decides $h_F$ in at most $F(\lfloor n/2 \rfloor)$ steps must be false. Hence, $h_F \notin \text{TIME}(F(\lfloor n/2 \rfloor))$. ◻

Conclusion

In this document, we have presented detailed proofs of two essential lemmas that are fundamental to establishing the Time Hierarchy Theorem. These lemmas demonstrate a separation between different time complexity classes using a carefully constructed language $h_F$.

Lemma 3 demonstrated that the language $h_F$, as defined in Definition [def:language_h_f], is decidable within the time complexity class $\text{TIME}(F(n)^3)$. This was achieved by constructing a universal Turing machine $U_F$ that can simulate any Turing machine $M$ on input $x$ and decide whether the pair $\langle M, x \rangle$ belongs to $h_F$ within the specified time bound. The analysis showed that the simulation can be performed in $\mathcal{O}(F(n)^3)$ time.
Lemma 4 showed that the same language $h_F$ cannot be decided within the time complexity class $\text{TIME}(F(\lfloor n/2 \rfloor))$. This was proven by contradiction, using a diagonalization argument to demonstrate that the existence of a Turing machine deciding $h_F$ in $\text{TIME}(F(\lfloor n/2 \rfloor))$ leads to a logical contradiction. The diagonalization technique is a powerful tool for proving lower bounds in complexity theory.

These results highlight the existence of a language ($h_F$) that can be decided in cubic time ($\mathcal{O}(F(n)^3)$) but not in a smaller time bound ($\mathcal{O}(F(\lfloor n/2 \rfloor))$) defined by the function $F$. This separation is a key element in understanding the hierarchy of time complexity classes.

The Time Hierarchy Theorem relies on the construction of a specific language, $h_F$, that serves as a witness to the separation between different time complexity classes. The language $h_F$ is designed such that it can be decided in $\mathcal{O}(F(n)^3)$ time but not in $\mathcal{O}(F(\lfloor n/2 \rfloor))$ time.
The proof of Lemma 4 employs a diagonalization argument, a common technique for proving lower bounds in complexity theory. This method involves constructing a machine ($D$) that behaves differently from all machines within a given class, leading to a contradiction. The machine $D$ is defined to accept if and only if $M_{h_F}$ rejects, creating the necessary contradiction.
The correction factor ($5n + 4$) in the definition of $F'(n)$ is crucial for the diagonalization argument in Lemma 4 to work correctly. It ensures that the simulation of Turing machines within the proof can be accurately analyzed and avoids a potential contradiction. Without this correction, the diagonalization argument would fail.

Follow-up Questions

The results presented here open up several avenues for further exploration and research:

How can we generalize the Time Hierarchy Theorem to other complexity classes, such as space complexity classes? The Space Hierarchy Theorem provides a similar result for space complexity.
What are the practical implications of the Time Hierarchy Theorem for the existence of efficient algorithms for certain computational problems? The theorem implies that there are problems that cannot be solved efficiently within certain time bounds, regardless of the algorithm used.
What are some open problems related to the Time Hierarchy Theorem and time complexity classes? There are many open questions regarding the exact relationships between different time complexity classes and the existence of intermediate classes.

In the next lecture, we will combine the results of these two lemmas to formally prove the full Time Hierarchy Theorem, demonstrating the strict inclusion of $\text{TIME}(F(n))$ in $\text{TIME}(F(n)^3)$. This will complete the proof and provide a clear understanding of the hierarchy of time complexity classes. The theorem will show that there are problems that can be solved in $\mathcal{O}(F(n)^3)$ time but not in $\mathcal{O}(F(n))$ time, establishing a strict hierarchy.

--- title: "Proof of the Time Hierarchy Theorem" author: "Your Name" date: "2025-01-28" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction This document presents a detailed proof of the Time Hierarchy Theorem, a fundamental result in complexity theory. This theorem establishes a strict hierarchy within time complexity classes, demonstrating that increasing the time bound allows us to solve strictly more problems. Specifically, the theorem states that for any proper time complexity function $F$, where $F(n) \geq n$, the complexity class $\text{TIME}(F(n))$ is strictly contained within $\text{TIME}(F(n)^3)$. The proof relies on the construction and analysis of a specific language, denoted as $h_F$. This language is carefully designed to serve as a witness to the separation between the complexity classes. The proof is structured around two key lemmas: - **Lemma [3](#lemma:hF_in_TIME_F_cubed){reference-type="ref" reference="lemma:hF_in_TIME_F_cubed"}:** Demonstrates that the language $h_F$ belongs to the complexity class $\text{TIME}(F(n)^3)$. - **Lemma [4](#lemma:hF_not_in_TIME_F_half){reference-type="ref" reference="lemma:hF_not_in_TIME_F_half"}:** Demonstrates that the language $h_F$ does not belong to the complexity class $\text{TIME}(F(\lfloor n/2 \rfloor))$. By proving these two lemmas, we establish that $h_F$ is a language that can be decided in $\mathcal{O}(F(n)^3)$ time but not in $\mathcal{O}(F(\lfloor n/2 \rfloor))$ time, thus proving the strict inclusion of $\text{TIME}(F(n))$ in $\text{TIME}(F(n)^3)$. This separation is achieved through a diagonalization argument, a common technique for proving lower bounds in complexity theory. The subsequent sections will provide the necessary definitions, detailed proofs of the two lemmas, and a concluding discussion. The proof also includes a crucial correction factor, $F'(n) = F(n) + 5n + 4$, in the definition of $h_F$, which is essential for the correctness of the argument. # Preliminaries This section introduces the essential definitions and notations required for the proof of the Time Hierarchy Theorem. These definitions lay the groundwork for the subsequent lemmas and the final theorem. ::: tcolorbox []{#def:proper_function label="def:proper_function"} A function $F: \mathbb{N} \to \mathbb{N}$ is considered *proper* if it satisfies the following conditions: 1. $F$ is non-decreasing, i.e., $F(n) \leq F(n+1)$ for all $n \in \mathbb{N}$. 2. There exists a Turing machine $M_F$ that, given an input $n$ (represented in unary as a string of $n$ ones), computes $F(n)$ in unary within $\mathcal{O}(F(n))$ time. **Significance:** Proper functions are essential because they represent realistic time complexity bounds that can be computed efficiently by a Turing machine. This property is crucial for the simulation arguments used in the proof. ::: ::: tcolorbox []{#def:language_h_f label="def:language_h_f"} Let $F$ be a proper function. The language $h_F$ is defined as the set of strings $mx$ such that the Turing machine $M$, when given input $x$, accepts within at most $F'(|x|)$ steps. Here, $F'(n)$ is defined as: $$F'(n) = F(n) + 5n + 4$$ where $|x|$ denotes the length of the string $x$. **Purpose:** The language $h_F$ is specifically constructed to serve as a witness for the separation of time complexity classes. It is designed such that it can be decided in $\mathcal{O}(F(n)^3)$ time but not in $\mathcal{O}(F(\lfloor n/2 \rfloor))$ time. ::: ::: tcolorbox []{#rem:f_prime label="rem:f_prime"} The function $F'(n) = F(n) + 5n + 4$ is a crucial component of the definition of $h_F$. The additional $5n+4$ term is a technical correction necessary for the diagonalization argument in Lemma [4](#lemma:hF_not_in_TIME_F_half){reference-type="ref" reference="lemma:hF_not_in_TIME_F_half"} to work correctly. This correction ensures that the simulation of Turing machines within the proof can be accurately analyzed and avoids a potential contradiction. Without this correction, the diagonalization argument would fail. ::: # Lemma 1: $h_F \in \text{TIME}(F(n)^3)$ {#lemma:hF_in_TIME_F_cubed} ::: tcolorbox []{#lemma:1_statement label="lemma:1_statement"} **Lemma 1:** If $F$ is a proper function such that $F(n) \geq n$, then the language $h_F$ belongs to the complexity class $\text{TIME}(F(n)^3)$. ::: ::: proof *Proof.* To prove this lemma, we will construct a universal Turing machine $U_F$ that decides the language $h_F$ within $\mathcal{O}(F(n)^3)$ time. This machine will simulate any given Turing machine $M$ on input $x$ for a limited number of steps determined by $F'(|x|)$. ## Construction of $U_F$ {#construction-of-u_f .unnumbered} The universal Turing machine $U_F$ takes as input a string of the form $\langle M, x \rangle$, where $M$ is the encoding of a Turing machine and $x$ is an input string for $M$. Let $n = |M| + |x|$ denote the total length of the input. The machine $U_F$ operates as follows: 1. **Compute** $F'(|x|)$: $U_F$ computes $F'(|x|) = F(|x|) + 5|x| + 4$ in unary on a dedicated working tape. Since $F$ is a proper function, $F'$ is also proper. Let $M_{F'}$ be a Turing machine that computes $F'(n)$ in unary in $\mathcal{O}(F'(n))$ time. $U_F$ simulates $M_{F'}$ on input $|x|$ to obtain $F'(|x|)$ in unary. This step takes $\mathcal{O}(F'(|x|)) = \mathcal{O}(F(|x|))$ time. Since $|x| \leq n$, this step is bounded by $\mathcal{O}(F(n))$. 2. **Store initial configuration:** $U_F$ stores the initial configuration of $M$ on input $x$ on another working tape, referred to as the configuration tape. This configuration includes the initial state of $M$, the initial head positions, and the content of all tapes of $M$. Initially, the first tape contains the input $x$, and all other tapes are blank. This step involves copying $x$ and adding a constant amount of information, taking $\mathcal{O}(n)$ time. 3. **Simulate $M$:** $U_F$ simulates the execution of $M$ on $x$ step by step. For each step of $M$, $U_F$ performs the following: 1. **Update configuration:** $U_F$ scans the configuration tape to determine the current state of $M$ and the symbols under the read heads. This takes time proportional to the length of the configuration tape. 2. **Find transition rule:** $U_F$ scans the encoding of $M$ (part of the input) to find the transition rule that corresponds to the current state and the symbols read. 3. **Apply transition:** $U_F$ applies the transition rule, updating the configuration tape to reflect the new state, head positions, and tape contents. This may involve shifting parts of the tape, which takes time proportional to the length of the configuration tape. After each step of $M$ is simulated, $U_F$ deletes one symbol from the tape containing $F'(|x|)$. 4. **Termination:** $U_F$ terminates with \"yes\" if $M$ reaches an accepting state before all symbols in $F'(|x|)$ are deleted. If all symbols in $F'(|x|)$ are deleted before $M$ reaches an accepting state, $U_F$ terminates with \"no\". ## Time Complexity Analysis {#time-complexity-analysis .unnumbered} Now, let's analyze the time complexity of each step: - **Step 1:** Computing $F'(|x|)$ takes $\mathcal{O}(F(n))$ time, as $F$ is a proper function. - **Step 2:** Storing the initial configuration takes $\mathcal{O}(n)$ time, as it involves copying the input $x$ and a constant amount of additional information. - **Step 3:** Updating the configuration: - Let $k$ be the number of tapes of $M$. The length of the configuration tape is at most $k \cdot F'(|x|)$, which is $\mathcal{O}(k \cdot F(|x|))$. Since $k$ is bounded by the length of the encoding of $M$, which is part of the input, we have $k \leq |M| \leq n$. Also, $|x| \leq n$. Thus, the length of the configuration tape is at most $\mathcal{O}(n \cdot F(n))$. Since $F(n) \geq n$, the length of the configuration tape is $\mathcal{O}(F(n)^2)$. - Each update of the configuration involves scanning and modifying the configuration tape, which takes time proportional to the length of the configuration tape, i.e., $\mathcal{O}(F(n)^2)$. - **Step 3**: The number of updates is at most $F'(|x|)$, which is $\mathcal{O}(F(|x|)) = \mathcal{O}(F(n))$. This is because $U_F$ simulates $M$ for at most $F'(|x|)$ steps. Therefore, the total time complexity of $U_F$ is: $$\mathcal{O}(F(n)) + \mathcal{O}(n) + \mathcal{O}(F(n)) \cdot \mathcal{O}(F(n)^2) = \mathcal{O}(F(n)^3)$$ Thus, we conclude that $h_F \in \text{TIME}(F(n)^3)$. ◻ ::: # Lemma 2: $h_F \notin \text{TIME}(F(\lfloor n/2 \rfloor))$ {#lemma:hF_not_in_TIME_F_half} ::: tcolorbox []{#lemma:2_statement label="lemma:2_statement"} **Lemma 2:** If $F$ is a proper function such that $F(n) \geq n$, then the language $h_F$ does not belong to the complexity class $\text{TIME}(F(\lfloor n/2 \rfloor))$. ::: ::: proof *Proof.* We will prove this lemma by contradiction using a diagonalization argument. Assume that there exists a Turing machine $M_{h_F}$ that decides the language $h_F$ in at most $F(\lfloor n/2 \rfloor)$ steps, where $n$ is the length of the input. This assumption will lead to a contradiction, proving that such a machine cannot exist. ## Construction of a Diagonalizing Machine $D$ {#construction-of-a-diagonalizing-machine-d .unnumbered} We define a Turing machine $D$ that takes as input the encoding of a Turing machine $M$ and operates as follows: 1. **Construct input:** $D$ constructs the input $\langle M, M \rangle$, which is the encoding of the pair consisting of the machine $M$ and the input $M$ (i.e., $M$ is given its own encoding as input). This step involves copying the input $M$. 2. **Simulate $M_{h_F}$:** $D$ simulates the execution of $M_{h_F}$ on the input $\langle M, M \rangle$. 3. **Diagonalize:** If $M_{h_F}$ accepts $\langle M, M \rangle$, then $D$ rejects. If $M_{h_F}$ rejects $\langle M, M \rangle$, then $D$ accepts. In essence, $D$ does the opposite of what $M_{h_F}$ does on the input $\langle M, M \rangle$. Thus, $D(M)$ accepts if and only if $M_{h_F}(M, M)$ rejects. This diagonalization step is crucial for creating a contradiction. ## Analysis of $D$ {#analysis-of-d .unnumbered} The behavior of $D$ is defined such that $D(M)$ accepts if and only if $M_{h_F}(M, M)$ rejects, which means that $\langle M, M \rangle \notin h_F$. This implies one of the following: - $M$ on input $M$ rejects. - $M$ on input $M$ accepts after more than $F'(|M|) = F(|M|) + 5|M| + 4$ steps. - $M$ on input $M$ does not halt. These conditions are a direct consequence of the definition of the language $h_F$. ## Contradiction {#contradiction .unnumbered} Now, let's consider the behavior of $D$ when given its own encoding as input, i.e., $D(D)$. This is the core of the diagonalization argument. - **Case 1: $D(D)$ accepts.** If $D(D)$ accepts, then by the definition of $D$, it means that $M_{h_F}(D, D)$ rejects. This implies that $\langle D, D \rangle \notin h_F$. However, if $\langle D, D \rangle \notin h_F$, then $D(D)$ must either reject or run for more than $F'(|D|)$ steps, which contradicts our assumption that $D(D)$ accepts. - **Case 2: $D(D)$ rejects.** If $D(D)$ rejects, then by the definition of $D$, it means that $M_{h_F}(D, D)$ accepts. This implies that $\langle D, D \rangle \in h_F$. However, if $\langle D, D \rangle \in h_F$, then $D(D)$ must accept within $F'(|D|)$ steps, which contradicts our assumption that $D(D)$ rejects. In both cases, we reach a contradiction, demonstrating that our initial assumption about the existence of $M_{h_F}$ must be false. ## Time Complexity of $D$ {#time-complexity-of-d .unnumbered} Let $n = |M|$ be the length of the input $M$. 1. **Constructing $\langle M, M \rangle$:** This step involves copying the string $M$, which takes $2n + 1$ steps (including a separator). Thus, this step takes $\mathcal{O}(n)$ time. 2. **Simulating $M_{h_F}$:** Simulating $M_{h_F}$ on $\langle M, M \rangle$ takes at most $F(\lfloor (2n+1)/2 \rfloor)$ steps, which is bounded by $F(n)$ steps. Therefore, the total time complexity of $D$ is $\mathcal{O}(n) + F(\lfloor (2n+1)/2 \rfloor) = \mathcal{O}(F(n))$. More precisely, the time complexity of $D$ is $F(n) + 5n + 4$. This is the crucial point where the correction factor $5n+4$ is used. If $D(D)$ accepts, it must do so in at most $F(|D|) + 5|D| + 4$ steps. However, if $D(D)$ accepts, it means that $M_{h_F}(D, D)$ rejects, so $\langle D, D \rangle \notin h_F$. This implies that $D(D)$ either rejects or runs for more than $F'(|D|)$ steps. This contradicts the assumption that $D(D)$ accepts in at most $F(|D|) + 5|D| + 4$ steps. Therefore, our initial assumption that there exists a machine $M_{h_F}$ that decides $h_F$ in at most $F(\lfloor n/2 \rfloor)$ steps must be false. Hence, $h_F \notin \text{TIME}(F(\lfloor n/2 \rfloor))$. ◻ ::: # Conclusion In this document, we have presented detailed proofs of two essential lemmas that are fundamental to establishing the Time Hierarchy Theorem. These lemmas demonstrate a separation between different time complexity classes using a carefully constructed language $h_F$. - **Lemma [3](#lemma:hF_in_TIME_F_cubed){reference-type="ref" reference="lemma:hF_in_TIME_F_cubed"}** demonstrated that the language $h_F$, as defined in Definition [\[def:language_h_f\]](#def:language_h_f){reference-type="ref" reference="def:language_h_f"}, is decidable within the time complexity class $\text{TIME}(F(n)^3)$. This was achieved by constructing a universal Turing machine $U_F$ that can simulate any Turing machine $M$ on input $x$ and decide whether the pair $\langle M, x \rangle$ belongs to $h_F$ within the specified time bound. The analysis showed that the simulation can be performed in $\mathcal{O}(F(n)^3)$ time. - **Lemma [4](#lemma:hF_not_in_TIME_F_half){reference-type="ref" reference="lemma:hF_not_in_TIME_F_half"}** showed that the same language $h_F$ cannot be decided within the time complexity class $\text{TIME}(F(\lfloor n/2 \rfloor))$. This was proven by contradiction, using a diagonalization argument to demonstrate that the existence of a Turing machine deciding $h_F$ in $\text{TIME}(F(\lfloor n/2 \rfloor))$ leads to a logical contradiction. The diagonalization technique is a powerful tool for proving lower bounds in complexity theory. These results highlight the existence of a language ($h_F$) that can be decided in cubic time ($\mathcal{O}(F(n)^3)$) but not in a smaller time bound ($\mathcal{O}(F(\lfloor n/2 \rfloor))$) defined by the function $F$. This separation is a key element in understanding the hierarchy of time complexity classes. ::: tcolorbox - The Time Hierarchy Theorem relies on the construction of a specific language, $h_F$, that serves as a witness to the separation between different time complexity classes. The language $h_F$ is designed such that it can be decided in $\mathcal{O}(F(n)^3)$ time but not in $\mathcal{O}(F(\lfloor n/2 \rfloor))$ time. - The proof of Lemma [4](#lemma:hF_not_in_TIME_F_half){reference-type="ref" reference="lemma:hF_not_in_TIME_F_half"} employs a diagonalization argument, a common technique for proving lower bounds in complexity theory. This method involves constructing a machine ($D$) that behaves differently from all machines within a given class, leading to a contradiction. The machine $D$ is defined to accept if and only if $M_{h_F}$ rejects, creating the necessary contradiction. - The correction factor ($5n + 4$) in the definition of $F'(n)$ is crucial for the diagonalization argument in Lemma [4](#lemma:hF_not_in_TIME_F_half){reference-type="ref" reference="lemma:hF_not_in_TIME_F_half"} to work correctly. It ensures that the simulation of Turing machines within the proof can be accurately analyzed and avoids a potential contradiction. Without this correction, the diagonalization argument would fail. ::: ## Follow-up Questions {#follow-up-questions .unnumbered} The results presented here open up several avenues for further exploration and research: - How can we generalize the Time Hierarchy Theorem to other complexity classes, such as space complexity classes? The Space Hierarchy Theorem provides a similar result for space complexity. - What are the practical implications of the Time Hierarchy Theorem for the existence of efficient algorithms for certain computational problems? The theorem implies that there are problems that cannot be solved efficiently within certain time bounds, regardless of the algorithm used. - What are some open problems related to the Time Hierarchy Theorem and time complexity classes? There are many open questions regarding the exact relationships between different time complexity classes and the existence of intermediate classes. In the next lecture, we will combine the results of these two lemmas to formally prove the full Time Hierarchy Theorem, demonstrating the strict inclusion of $\text{TIME}(F(n))$ in $\text{TIME}(F(n)^3)$. This will complete the proof and provide a clear understanding of the hierarchy of time complexity classes. The theorem will show that there are problems that can be solved in $\mathcal{O}(F(n)^3)$ time but not in $\mathcal{O}(F(n))$ time, establishing a strict hierarchy.

Proof of the Time Hierarchy Theorem

Introduction

Preliminaries

Lemma 1: \(h_F \in \text{TIME}(F(n)^3)\)

Construction of \(U_F\)

Time Complexity Analysis

Lemma 2: \(h_F \notin \text{TIME}(F(\lfloor n/2 \rfloor))\)

Construction of a Diagonalizing Machine \(D\)

Analysis of \(D\)

Contradiction

Time Complexity of \(D\)

Conclusion

Follow-up Questions