Lecture Notes: Undecidability, Complexity Classes, and Proper Complexity Functions

Author

Your Name

Published

January 28, 2025

Introduction

This lecture introduces fundamental concepts in computational complexity theory, focusing on undecidability, complexity classes, and proper complexity functions. We begin by exploring undecidability, which concerns the limitations of algorithmic computation, specifically problems that cannot be solved by Turing machines that always halt. This includes an overview of the Halting Problem and its implications. We then examine various complexity classes, including deterministic and non-deterministic time and space classes, and discuss their relationships, particularly the distinction between deterministic and non-deterministic computation. A key focus of this lecture is the concept of proper complexity functions, which are essential for defining meaningful complexity classes and for proving important theorems like the hierarchy theorem and the gap theorem. These theorems demonstrate how proper complexity functions are crucial for understanding the relationships between different complexity classes, highlighting the nuances of computational resource usage. We will also touch upon the concept of precise Turing machines and their role in analyzing complexity.

Complements of Non-Deterministic Complexity Classes

Complexity Classes

A complexity class is a collection of languages that can be decided by a Turing machine using a specific amount of computational resources. These resources are typically measured in terms of time or space, and the amount is expressed as a function of the input size, $n$. For instance, $\text{time}(f(n))$ denotes the class of languages decidable in time $f(n)$ by a deterministic Turing machine, and $\text{nondeterministic-time}(f(n))$ denotes the class of languages decidable in time $f(n)$ by a non-deterministic Turing machine.

Complement of a Language

Given a language $L$, which is a set of strings over a given alphabet, its complement, denoted by $\overline{L}$, is the set of all strings over the same alphabet that are not in $L$. In the context of decision problems, where the goal is to determine whether a given input belongs to a language, $L$ represents the set of inputs for which the answer is "yes," while $\overline{L}$ represents the set of inputs for which the answer is "no."

Palindrome Language: Consider the language of palindromes, which consists of strings that read the same forwards and backward. The complement of this language is the set of all strings that are not palindromes.

Reachability Problem: The reachability problem in a graph involves determining whether a path exists between two given nodes. The reachability language can be defined as: \[\text{Reachability} = \{ \langle G, u, v \rangle \mid u \text{ can reach } v \text{ in graph } G \}\] where $\langle G, u, v \rangle$ represents an encoding of the graph $G$ and the nodes $u$ and $v$. The complement of the reachability language, denoted as $\overline{\text{Reachability}}$, includes all strings that do not represent valid graph encodings, as well as strings representing graphs where $u$ cannot reach $v$: \[\overline{\text{Reachability}} = \{ \langle G, u, v \rangle \mid u \text{ cannot reach } v \text{ in graph } G \} \cup \{ \text{invalid encodings} \}\]

Complement of a Complexity Class

The complement of a complexity class $C$, denoted as $\text{co-}C$, is the set of all languages that are complements of languages in $C$. Formally: \[\text{co-}C = \{ \overline{L} \mid L \in C \}\]

If $C = \text{time}(n^3)$, then $\text{co-time}(n^3)$ is the set of all languages whose complements can be decided in time $n^3$. \[\text{co-time}(n^3) = \{ \overline{L} \mid L \in \text{time}(n^3) \}\]

Deterministic Complexity Classes

For deterministic complexity classes, the complement operation does not change the class. This is because if a language $L$ can be decided by a deterministic Turing machine in time $f(n)$ or space $f(n)$, then its complement $\overline{L}$ can also be decided by a deterministic Turing machine within the same time or space bounds. This is achieved by simply switching the accepting and rejecting states of the original machine. Thus: \[\text{co-time}(f(n)) = \text{time}(f(n))\] \[\text{co-space}(f(n)) = \text{space}(f(n))\]

Non-Deterministic Complexity Classes

The relationship between a non-deterministic complexity class and its complement is not as straightforward as in the deterministic case. A non-deterministic Turing machine accepts a string if at least one computation path leads to an accepting state. It rejects a string only if all computation paths lead to a rejecting state.

If we attempt to create a machine for the complement language by simply switching accepting and rejecting states, the resulting machine might not correctly decide the complement language. This is because the existence of at least one accepting path in the original machine does not imply that all paths are rejecting in the modified machine, and vice versa.

A prominent example of this is the relationship between the complexity classes $\text{NP}$ (Non-deterministic Polynomial time) and $\text{co-NP}$. The question of whether $\text{NP} = \text{co-NP}$ is a major open problem in complexity theory. This highlights the asymmetry between acceptance and rejection in non-deterministic computation.

Proper Complexity Functions

Motivation

The concept of a proper complexity function is crucial for defining meaningful complexity classes and avoiding pathological cases. If we were to use arbitrary functions to define complexity classes, we might encounter situations where the function itself is too complex to compute, making the defined complexity class difficult to analyze or even meaningless. Therefore, we need to restrict the class of functions used to define complexity classes to those that are "well-behaved" in terms of computability and resource usage. This ensures that the complexity classes we define are based on functions that are themselves computationally tractable.

Intuitive Definition

Intuitively, a proper complexity function $f(n)$ should satisfy the following properties:

Computability: The function $f(n)$ must be computable by a Turing machine. This means there exists a Turing machine $M_f$ that, given an input of length $n$, can compute the value of $f(n)$.
Non-decreasing: The function $f(n)$ must be non-decreasing, meaning that $f(n+1) \geq f(n)$ for all $n$. This ensures that as the input size increases, the resource bound also increases (or at least does not decrease), reflecting the intuitive notion that larger inputs should not require less resources.
Efficient Computability: The function $f(n)$ must be computable without requiring excessive amounts of time or space. This prevents the function from being more complex than the complexity classes it is used to define, ensuring that the resource bounds are meaningful.

Formal Definition

A function $f: \mathbb{N} \rightarrow \mathbb{N}$ is considered a proper complexity function if there exists a Turing machine $M_f$ that, for any input string $x$ of length $n$, satisfies the following conditions:

Unary Output: $M_f$ terminates with the value $f(n)$ written in unary on its output tape. This means that $f(n)$ is represented by a sequence of $f(n)$ symbols (e.g., ’1’s) followed by a blank. This representation is useful as a "yardstick" for counting steps in other computations.
Time Complexity: The number of steps $T$ taken by $M_f$ to compute $f(n)$ is bounded by $O(f(n) + n)$. The term $+n$ is included because the machine needs to read the input of length $n$. This ensures that the computation of $f(n)$ does not take significantly more time than the function’s value itself, especially for functions that grow slower than linear.
Space Complexity: The space $S$ used by $M_f$ during the computation is bounded by $O(f(n))$. This ensures that the computation of $f(n)$ does not require significantly more space than the function’s value.
Input Independence: The time $T$ and space $S$ used by $M_f$ depend only on the length $n$ of the input string $x$ and not on the specific content of $x$. This means that for all input strings of the same length, the machine uses the same amount of time and space to compute $f(n)$. This ensures that the computation of $f(n)$ is consistent across all inputs of the same size.

A function $f: \mathbb{N} \rightarrow \mathbb{N}$ is a proper complexity function if there exists a Turing machine $M_f$ such that for any input string $x$ of length $n$:

$M_f$ on input $x$ terminates with output $f(n)$ written in unary.
The number of steps $T$ taken by $M_f$ is $O(f(n) + n)$.
The space $S$ used by $M_f$ is $O(f(n))$.
$T$ and $S$ depend only on $n$ (the length of $x$) and not on the specific content of $x$.

Examples

Many commonly used functions in complexity theory are proper complexity functions. Some examples include:

Constant Functions: $f(n) = c$, where $c$ is a constant.
Logarithmic Functions: $f(n) = \log n$.
Polynomial Functions: $f(n) = n^k$, where $k$ is a positive constant.
Exponential Functions: $f(n) = 2^n$.
Exponential of Polynomial Functions: $f(n) = 2^{n^k}$, where $k$ is a positive constant.

Furthermore, proper complexity functions are closed under various operations. If $f(n)$ and $g(n)$ are proper complexity functions, then the following functions are also proper:

Composition: $f(g(n))$.
Addition: $f(n) + g(n)$.
Multiplication: $f(n) \cdot g(n)$.
Exponentiation: $f(n)^{g(n)}$.

These closure properties ensure that we can construct more complex proper complexity functions from simpler ones, allowing us to define a wide range of complexity classes.

Precise Turing Machines

Definition 1.

A Turing machine $M$ is considered precise if there exist proper complexity functions $f$ and $g$ such that, for any input of length $n$, $M$ always terminates in exactly $f(n)$ steps and uses exactly $g(n)$ space.

Theorem 1.

If $f$ is a proper complexity function and a Turing machine $M$ decides a language $L$ in time $f(n)$, then there exists a precise Turing machine $M'$ that decides $L$ in time $O(f(n))$.

Proof. Proof. Let $M$ be a Turing machine that decides a language $L$ in time $f(n)$. This means that for any input $x$ of length $n$, $M$ terminates in at most $f(n)$ steps. We will construct a precise Turing machine $M'$ that decides the same language $L$ and always terminates in $O(f(n))$ steps.

The machine $M'$ operates as follows:

Compute Input Length: On input $x$ of length $n$, $M'$ first computes the length $n$ of the input $x$ and writes it in binary on a dedicated tape. This step takes $O(n)$ time.
Compute $f(n)$: $M'$ then simulates the Turing machine $M_f$ (which exists because $f$ is a proper complexity function) to compute $f(n)$ in unary on another dedicated tape. The input to $M_f$ is the binary representation of $n$ computed in the previous step. Let $T$ be the number of steps taken by $M_f$. According to the definition of a proper complexity function, $T = O(f(n) + n)$ and $T$ depends only on $n$.
Simulate $M$ and Count Steps: $M'$ then simulates the original machine $M$ on the input $x$. Simultaneously, for each step of $M$, $M'$ removes one symbol from the unary representation of $f(n)$ on the dedicated tape.
Complete the Count: If $M$ terminates before all symbols from the unary representation of $f(n)$ are removed, $M'$ continues to remove the remaining symbols one by one until none are left.

Schematic of the precise Turing machine (M').

The total number of steps taken by $M'$ is the sum of the steps taken to compute the length of the input, the steps taken to compute $f(n)$, and the steps taken to simulate $M$ and remove any remaining symbols. This is given by $O(n) + T + f(n)$. Since $T = O(f(n) + n)$, the total number of steps is $O(n) + O(f(n) + n) + f(n) = O(f(n) + n) = O(f(n))$, because $f(n)$ is non-decreasing and therefore $f(n) \geq n$ for sufficiently large $n$.

Since $M'$ always takes $O(f(n))$ steps, regardless of the specific input $x$ of length $n$, $M'$ is a precise Turing machine. ◻

Exercise: Find the small mistake in the proof. Detail missing: The proof assumes that the machine $M_f$ starts with the input $x$ on its tape, but in reality, $M_f$ needs to receive the length of $x$ as input. The machine $M'$ needs to compute the length of $x$ and provide it as input to $M_f$. This step is missing in the proof description.

Hierarchy Theorem

Universal Turing Machines

A universal Turing machine (UTM), denoted by $U$, is a Turing machine that can simulate the behavior of any other Turing machine $M$ given a suitable encoding of $M$ and its input $x$. The encoding of $M$, denoted by $\langle M \rangle$, typically includes a description of its states, alphabet, transition function, and starting state. The UTM takes as input the pair $\langle \langle M \rangle, x \rangle$ and simulates the execution of $M$ on $x$. This simulation involves interpreting the encoded description of $M$ and applying its transition function to the input $x$, effectively mimicking the behavior of $M$.

Halting Problem

The Halting Problem is a decision problem defined by the language: \[H = \{ \langle M, x \rangle \mid M \text{ is a Turing machine that halts on input } x \}\] where $\langle M, x \rangle$ represents an encoding of the Turing machine $M$ and its input $x$. The Halting Theorem, a fundamental result in computability theory, states that the language $H$ is undecidable. This means that there exists no Turing machine that can decide whether an arbitrary Turing machine $M$ will halt on a given input $x$. The proof of this theorem typically involves a diagonalization argument, showing that any hypothetical machine that decides $H$ would lead to a contradiction.

Quantitative Version of the Halting Problem

To explore the hierarchy of complexity classes, we define a family of languages $H_f$ parameterized by a proper complexity function $f$. This language is a quantitative version of the halting problem, where we consider whether a Turing machine accepts an input within a specific time bound: \[H_f = \{ \langle M, x \rangle \mid M \text{ accepts } x \text{ within } f(|x|) \text{ steps} \}\] Here, $|x|$ denotes the length of the input string $x$, and $f(|x|)$ represents the time bound within which we are checking if $M$ accepts $x$. This language is decidable because we can simulate $M$ on $x$ for at most $f(|x|)$ steps. If $M$ accepts within this bound, the pair is in $H_f$; otherwise, it is not.

Theorem 2 (Hierarchy Theorem). For any proper complexity function $f$, there exists a language $H_f$ such that: \[H_f \in \text{TIME}(f(n)^3) \quad \text{and} \quad H_f \notin \text{TIME}(f(n)).\]

Detail missing: The proof of the Hierarchy Theorem is not provided here, as it requires understanding the proof of the Halting Theorem by diagonalization, which is presented in Chapter 3 of the book. The key idea is that we can construct a machine that simulates another machine for a given number of steps, and then use a diagonalization argument to show that there is a language that can be decided in time $f(n)^3$ but not in time $f(n)$. This theorem demonstrates that there are problems that can be solved within a certain time bound but cannot be solved within a smaller time bound, establishing a hierarchy of complexity classes. Specifically, it shows that by increasing the time bound from $f(n)$ to $f(n)^3$, we can solve strictly more problems, indicating that $\text{TIME}(f(n))$ is a proper subset of $\text{TIME}(f(n)^3)$.

Conclusion

In this lecture, we have covered several key concepts in computational complexity theory. We began by discussing undecidability, focusing on the limitations of Turing machines and the existence of problems that cannot be algorithmically solved, such as the Halting Problem. We then explored the concept of complexity classes, including deterministic and non-deterministic time and space classes, and examined the subtle differences between a complexity class and its complement, particularly in the context of non-deterministic classes. We highlighted the open problem of whether $\text{NP} = \text{co-NP}$, which remains a significant question in complexity theory.

A significant portion of the lecture was dedicated to proper complexity functions, which are essential for defining meaningful complexity classes. We discussed the formal definition of proper complexity functions, their properties, and provided several examples, emphasizing their role in ensuring that complexity classes are based on computationally tractable functions. We also introduced the concept of precise Turing machines and demonstrated how any Turing machine operating within a time bound defined by a proper complexity function can be transformed into a precise Turing machine that always terminates in the same amount of time for inputs of the same length. This transformation is crucial for theoretical analysis and for understanding the behavior of algorithms.

Finally, we introduced the hierarchy theorem, a quantitative version of the halting theorem, which demonstrates the existence of a hierarchy among complexity classes defined by proper functions. This theorem shows that for any proper complexity function $f$, there are languages that can be decided in time $f(n)^3$ but not in time $f(n)$, establishing a clear separation between different time complexity classes. This result is fundamental for understanding the limitations of computation and the structure of complexity classes.

For the next lecture, it is crucial to review Chapter 3 of the textbook, paying particular attention to the proof of the halting theorem using diagonalization. This proof is fundamental for understanding the hierarchy theorem, which we will discuss in more detail next time. The diagonalization technique is a powerful tool in computability and complexity theory, and a thorough understanding of it is essential for grasping the concepts we will cover.

Additionally, please consider the following questions:

How does the hierarchy theorem demonstrate the existence of a hierarchy within the class P (Polynomial Time)? In other words, can we find problems that are in P but require increasingly higher polynomial time bounds? This question explores the practical implications of the hierarchy theorem within the class of problems considered tractable.
What is the significance of the gap theorem, and how does it contrast with the hierarchy theorem? The gap theorem suggests that there exist functions for which the corresponding time complexity class is the same as a much larger complexity class, which seems to contradict the hierarchy theorem. Understanding the conditions under which each theorem applies is crucial for a complete picture of complexity theory.
Can you think of other examples of proper complexity functions and their applications in defining complexity classes? How do these functions relate to the resources required by Turing machines? This question encourages you to think critically about the relationship between complexity functions and the computational resources they represent.

These questions will help solidify your understanding of the material and prepare you for our next discussion, where we will delve deeper into the implications of these results and explore related topics.

--- title: "Lecture Notes: Undecidability, Complexity Classes, and Proper Complexity Functions" 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 lecture introduces fundamental concepts in computational complexity theory, focusing on undecidability, complexity classes, and proper complexity functions. We begin by exploring undecidability, which concerns the limitations of algorithmic computation, specifically problems that cannot be solved by Turing machines that always halt. This includes an overview of the Halting Problem and its implications. We then examine various complexity classes, including deterministic and non-deterministic time and space classes, and discuss their relationships, particularly the distinction between deterministic and non-deterministic computation. A key focus of this lecture is the concept of proper complexity functions, which are essential for defining meaningful complexity classes and for proving important theorems like the hierarchy theorem and the gap theorem. These theorems demonstrate how proper complexity functions are crucial for understanding the relationships between different complexity classes, highlighting the nuances of computational resource usage. We will also touch upon the concept of precise Turing machines and their role in analyzing complexity. # Complements of Non-Deterministic Complexity Classes ## Complexity Classes A complexity class is a collection of languages that can be decided by a Turing machine using a specific amount of computational resources. These resources are typically measured in terms of time or space, and the amount is expressed as a function of the input size, $n$. For instance, $\text{time}(f(n))$ denotes the class of languages decidable in time $f(n)$ by a deterministic Turing machine, and $\text{nondeterministic-time}(f(n))$ denotes the class of languages decidable in time $f(n)$ by a non-deterministic Turing machine. ## Complement of a Language Given a language $L$, which is a set of strings over a given alphabet, its complement, denoted by $\overline{L}$, is the set of all strings over the same alphabet that are not in $L$. In the context of decision problems, where the goal is to determine whether a given input belongs to a language, $L$ represents the set of inputs for which the answer is \"yes,\" while $\overline{L}$ represents the set of inputs for which the answer is \"no.\" ::: tcolorbox **Palindrome Language:** Consider the language of palindromes, which consists of strings that read the same forwards and backward. The complement of this language is the set of all strings that are not palindromes. ::: ::: tcolorbox **Reachability Problem:** The reachability problem in a graph involves determining whether a path exists between two given nodes. The reachability language can be defined as: $$\text{Reachability} = \{ \langle G, u, v \rangle \mid u \text{ can reach } v \text{ in graph } G \}$$ where $\langle G, u, v \rangle$ represents an encoding of the graph $G$ and the nodes $u$ and $v$. The complement of the reachability language, denoted as $\overline{\text{Reachability}}$, includes all strings that do not represent valid graph encodings, as well as strings representing graphs where $u$ cannot reach $v$: $$\overline{\text{Reachability}} = \{ \langle G, u, v \rangle \mid u \text{ cannot reach } v \text{ in graph } G \} \cup \{ \text{invalid encodings} \}$$ ::: ## Complement of a Complexity Class The complement of a complexity class $C$, denoted as $\text{co-}C$, is the set of all languages that are complements of languages in $C$. Formally: $$\text{co-}C = \{ \overline{L} \mid L \in C \}$$ ::: tcolorbox If $C = \text{time}(n^3)$, then $\text{co-time}(n^3)$ is the set of all languages whose complements can be decided in time $n^3$. $$\text{co-time}(n^3) = \{ \overline{L} \mid L \in \text{time}(n^3) \}$$ ::: ## Deterministic Complexity Classes For deterministic complexity classes, the complement operation does not change the class. This is because if a language $L$ can be decided by a deterministic Turing machine in time $f(n)$ or space $f(n)$, then its complement $\overline{L}$ can also be decided by a deterministic Turing machine within the same time or space bounds. This is achieved by simply switching the accepting and rejecting states of the original machine. Thus: $$\text{co-time}(f(n)) = \text{time}(f(n))$$ $$\text{co-space}(f(n)) = \text{space}(f(n))$$ ## Non-Deterministic Complexity Classes The relationship between a non-deterministic complexity class and its complement is not as straightforward as in the deterministic case. A non-deterministic Turing machine accepts a string if at least one computation path leads to an accepting state. It rejects a string only if all computation paths lead to a rejecting state. If we attempt to create a machine for the complement language by simply switching accepting and rejecting states, the resulting machine might not correctly decide the complement language. This is because the existence of at least one accepting path in the original machine does not imply that all paths are rejecting in the modified machine, and vice versa. A prominent example of this is the relationship between the complexity classes $\text{NP}$ (Non-deterministic Polynomial time) and $\text{co-NP}$. The question of whether $\text{NP} = \text{co-NP}$ is a major open problem in complexity theory. This highlights the asymmetry between acceptance and rejection in non-deterministic computation. # Proper Complexity Functions ## Motivation The concept of a proper complexity function is crucial for defining meaningful complexity classes and avoiding pathological cases. If we were to use arbitrary functions to define complexity classes, we might encounter situations where the function itself is too complex to compute, making the defined complexity class difficult to analyze or even meaningless. Therefore, we need to restrict the class of functions used to define complexity classes to those that are \"well-behaved\" in terms of computability and resource usage. This ensures that the complexity classes we define are based on functions that are themselves computationally tractable. ## Intuitive Definition Intuitively, a proper complexity function $f(n)$ should satisfy the following properties: 1. **Computability:** The function $f(n)$ must be computable by a Turing machine. This means there exists a Turing machine $M_f$ that, given an input of length $n$, can compute the value of $f(n)$. 2. **Non-decreasing:** The function $f(n)$ must be non-decreasing, meaning that $f(n+1) \geq f(n)$ for all $n$. This ensures that as the input size increases, the resource bound also increases (or at least does not decrease), reflecting the intuitive notion that larger inputs should not require less resources. 3. **Efficient Computability:** The function $f(n)$ must be computable without requiring excessive amounts of time or space. This prevents the function from being more complex than the complexity classes it is used to define, ensuring that the resource bounds are meaningful. ## Formal Definition A function $f: \mathbb{N} \rightarrow \mathbb{N}$ is considered a **proper complexity function** if there exists a Turing machine $M_f$ that, for any input string $x$ of length $n$, satisfies the following conditions: 1. **Unary Output:** $M_f$ terminates with the value $f(n)$ written in unary on its output tape. This means that $f(n)$ is represented by a sequence of $f(n)$ symbols (e.g., '1's) followed by a blank. This representation is useful as a \"yardstick\" for counting steps in other computations. 2. **Time Complexity:** The number of steps $T$ taken by $M_f$ to compute $f(n)$ is bounded by $O(f(n) + n)$. The term $+n$ is included because the machine needs to read the input of length $n$. This ensures that the computation of $f(n)$ does not take significantly more time than the function's value itself, especially for functions that grow slower than linear. 3. **Space Complexity:** The space $S$ used by $M_f$ during the computation is bounded by $O(f(n))$. This ensures that the computation of $f(n)$ does not require significantly more space than the function's value. 4. **Input Independence:** The time $T$ and space $S$ used by $M_f$ depend only on the length $n$ of the input string $x$ and not on the specific content of $x$. This means that for all input strings of the same length, the machine uses the same amount of time and space to compute $f(n)$. This ensures that the computation of $f(n)$ is consistent across all inputs of the same size. ::: tcolorbox A function $f: \mathbb{N} \rightarrow \mathbb{N}$ is a **proper complexity function** if there exists a Turing machine $M_f$ such that for any input string $x$ of length $n$: 1. $M_f$ on input $x$ terminates with output $f(n)$ written in unary. 2. The number of steps $T$ taken by $M_f$ is $O(f(n) + n)$. 3. The space $S$ used by $M_f$ is $O(f(n))$. 4. $T$ and $S$ depend only on $n$ (the length of $x$) and not on the specific content of $x$. ::: ## Examples Many commonly used functions in complexity theory are proper complexity functions. Some examples include: - **Constant Functions:** $f(n) = c$, where $c$ is a constant. - **Logarithmic Functions:** $f(n) = \log n$. - **Polynomial Functions:** $f(n) = n^k$, where $k$ is a positive constant. - **Exponential Functions:** $f(n) = 2^n$. - **Exponential of Polynomial Functions:** $f(n) = 2^{n^k}$, where $k$ is a positive constant. Furthermore, proper complexity functions are closed under various operations. If $f(n)$ and $g(n)$ are proper complexity functions, then the following functions are also proper: - **Composition:** $f(g(n))$. - **Addition:** $f(n) + g(n)$. - **Multiplication:** $f(n) \cdot g(n)$. - **Exponentiation:** $f(n)^{g(n)}$. These closure properties ensure that we can construct more complex proper complexity functions from simpler ones, allowing us to define a wide range of complexity classes. # Precise Turing Machines :::: definition **Definition 1**. ::: tcolorbox *A Turing machine $M$ is considered **precise** if there exist proper complexity functions $f$ and $g$ such that, for any input of length $n$, $M$ always terminates in exactly $f(n)$ steps and uses exactly $g(n)$ space.* ::: :::: :::: {.thm:precise_tm .theorem} **Theorem 1**. ::: tcolorbox *If $f$ is a proper complexity function and a Turing machine $M$ decides a language $L$ in time $f(n)$, then there exists a precise Turing machine $M'$ that decides $L$ in time $O(f(n))$.* ::: :::: ::: proof *Proof.* Let $M$ be a Turing machine that decides a language $L$ in time $f(n)$. This means that for any input $x$ of length $n$, $M$ terminates in at most $f(n)$ steps. We will construct a precise Turing machine $M'$ that decides the same language $L$ and always terminates in $O(f(n))$ steps. The machine $M'$ operates as follows: 1. **Compute Input Length:** On input $x$ of length $n$, $M'$ first computes the length $n$ of the input $x$ and writes it in binary on a dedicated tape. This step takes $O(n)$ time. 2. **Compute $f(n)$:** $M'$ then simulates the Turing machine $M_f$ (which exists because $f$ is a proper complexity function) to compute $f(n)$ in unary on another dedicated tape. The input to $M_f$ is the binary representation of $n$ computed in the previous step. Let $T$ be the number of steps taken by $M_f$. According to the definition of a proper complexity function, $T = O(f(n) + n)$ and $T$ depends only on $n$. 3. **Simulate $M$ and Count Steps:** $M'$ then simulates the original machine $M$ on the input $x$. Simultaneously, for each step of $M$, $M'$ removes one symbol from the unary representation of $f(n)$ on the dedicated tape. 4. **Complete the Count:** If $M$ terminates before all symbols from the unary representation of $f(n)$ are removed, $M'$ continues to remove the remaining symbols one by one until none are left. <figure id="fig:precise_tm"> <figcaption>Schematic of the precise Turing machine <span class="math inline">$M'$</span>.</figcaption> </figure> The total number of steps taken by $M'$ is the sum of the steps taken to compute the length of the input, the steps taken to compute $f(n)$, and the steps taken to simulate $M$ and remove any remaining symbols. This is given by $O(n) + T + f(n)$. Since $T = O(f(n) + n)$, the total number of steps is $O(n) + O(f(n) + n) + f(n) = O(f(n) + n) = O(f(n))$, because $f(n)$ is non-decreasing and therefore $f(n) \geq n$ for sufficiently large $n$. Since $M'$ always takes $O(f(n))$ steps, regardless of the specific input $x$ of length $n$, $M'$ is a precise Turing machine. ◻ ::: **Exercise:** Find the small mistake in the proof. *Detail missing: The proof assumes that the machine $M_f$ starts with the input $x$ on its tape, but in reality, $M_f$ needs to receive the length of $x$ as input. The machine $M'$ needs to compute the length of $x$ and provide it as input to $M_f$. This step is missing in the proof description.* # Hierarchy Theorem ## Universal Turing Machines A universal Turing machine (UTM), denoted by $U$, is a Turing machine that can simulate the behavior of any other Turing machine $M$ given a suitable encoding of $M$ and its input $x$. The encoding of $M$, denoted by $\langle M \rangle$, typically includes a description of its states, alphabet, transition function, and starting state. The UTM takes as input the pair $\langle \langle M \rangle, x \rangle$ and simulates the execution of $M$ on $x$. This simulation involves interpreting the encoded description of $M$ and applying its transition function to the input $x$, effectively mimicking the behavior of $M$. ## Halting Problem The Halting Problem is a decision problem defined by the language: $$H = \{ \langle M, x \rangle \mid M \text{ is a Turing machine that halts on input } x \}$$ where $\langle M, x \rangle$ represents an encoding of the Turing machine $M$ and its input $x$. The Halting Theorem, a fundamental result in computability theory, states that the language $H$ is undecidable. This means that there exists no Turing machine that can decide whether an arbitrary Turing machine $M$ will halt on a given input $x$. The proof of this theorem typically involves a diagonalization argument, showing that any hypothetical machine that decides $H$ would lead to a contradiction. ## Quantitative Version of the Halting Problem To explore the hierarchy of complexity classes, we define a family of languages $H_f$ parameterized by a proper complexity function $f$. This language is a quantitative version of the halting problem, where we consider whether a Turing machine accepts an input within a specific time bound: $$H_f = \{ \langle M, x \rangle \mid M \text{ accepts } x \text{ within } f(|x|) \text{ steps} \}$$ Here, $|x|$ denotes the length of the input string $x$, and $f(|x|)$ represents the time bound within which we are checking if $M$ accepts $x$. This language is decidable because we can simulate $M$ on $x$ for at most $f(|x|)$ steps. If $M$ accepts within this bound, the pair is in $H_f$; otherwise, it is not. :::: tcolorbox ::: {.thm:hierarchy_theorem .theorem} **Theorem 2** (Hierarchy Theorem). *For any proper complexity function $f$, there exists a language $H_f$ such that: $$H_f \in \text{TIME}(f(n)^3) \quad \text{and} \quad H_f \notin \text{TIME}(f(n)).$$* ::: :::: *Detail missing: The proof of the Hierarchy Theorem is not provided here, as it requires understanding the proof of the Halting Theorem by diagonalization, which is presented in Chapter 3 of the book. The key idea is that we can construct a machine that simulates another machine for a given number of steps, and then use a diagonalization argument to show that there is a language that can be decided in time $f(n)^3$ but not in time $f(n)$. This theorem demonstrates that there are problems that can be solved within a certain time bound but cannot be solved within a smaller time bound, establishing a hierarchy of complexity classes. Specifically, it shows that by increasing the time bound from $f(n)$ to $f(n)^3$, we can solve strictly more problems, indicating that $\text{TIME}(f(n))$ is a proper subset of $\text{TIME}(f(n)^3)$.* # Conclusion In this lecture, we have covered several key concepts in computational complexity theory. We began by discussing undecidability, focusing on the limitations of Turing machines and the existence of problems that cannot be algorithmically solved, such as the Halting Problem. We then explored the concept of complexity classes, including deterministic and non-deterministic time and space classes, and examined the subtle differences between a complexity class and its complement, particularly in the context of non-deterministic classes. We highlighted the open problem of whether $\text{NP} = \text{co-NP}$, which remains a significant question in complexity theory. A significant portion of the lecture was dedicated to proper complexity functions, which are essential for defining meaningful complexity classes. We discussed the formal definition of proper complexity functions, their properties, and provided several examples, emphasizing their role in ensuring that complexity classes are based on computationally tractable functions. We also introduced the concept of precise Turing machines and demonstrated how any Turing machine operating within a time bound defined by a proper complexity function can be transformed into a precise Turing machine that always terminates in the same amount of time for inputs of the same length. This transformation is crucial for theoretical analysis and for understanding the behavior of algorithms. Finally, we introduced the hierarchy theorem, a quantitative version of the halting theorem, which demonstrates the existence of a hierarchy among complexity classes defined by proper functions. This theorem shows that for any proper complexity function $f$, there are languages that can be decided in time $f(n)^3$ but not in time $f(n)$, establishing a clear separation between different time complexity classes. This result is fundamental for understanding the limitations of computation and the structure of complexity classes. For the next lecture, it is crucial to review Chapter 3 of the textbook, paying particular attention to the proof of the halting theorem using diagonalization. This proof is fundamental for understanding the hierarchy theorem, which we will discuss in more detail next time. The diagonalization technique is a powerful tool in computability and complexity theory, and a thorough understanding of it is essential for grasping the concepts we will cover. Additionally, please consider the following questions: - How does the hierarchy theorem demonstrate the existence of a hierarchy within the class P (Polynomial Time)? In other words, can we find problems that are in P but require increasingly higher polynomial time bounds? This question explores the practical implications of the hierarchy theorem within the class of problems considered tractable. - What is the significance of the gap theorem, and how does it contrast with the hierarchy theorem? The gap theorem suggests that there exist functions for which the corresponding time complexity class is the same as a much larger complexity class, which seems to contradict the hierarchy theorem. Understanding the conditions under which each theorem applies is crucial for a complete picture of complexity theory. - Can you think of other examples of proper complexity functions and their applications in defining complexity classes? How do these functions relate to the resources required by Turing machines? This question encourages you to think critically about the relationship between complexity functions and the computational resources they represent. These questions will help solidify your understanding of the material and prepare you for our next discussion, where we will delve deeper into the implications of these results and explore related topics.