Lecture Notes: Non-deterministic Turing Machines and Complexity Classes

Author

Your Name

Published

January 28, 2025

Introduction

This lecture introduces the concept of non-deterministic Turing machines and explores their relationship to deterministic Turing machines. We will also define and discuss several important complexity classes. The lecture begins with a discussion of the Random Access Machine (RAM) model, highlighting its similarities and differences with Turing machines, particularly in terms of memory access and instruction sets. We then formally define non-deterministic Turing machines (NDTMs), contrasting them with their deterministic counterparts by focusing on the transition relation versus the transition function. The reachability problem is introduced as a practical example to illustrate the differences in computational power and space requirements between deterministic and non-deterministic models. Finally, we define key complexity classes such as P, NP, PSPACE, NPSPACE, L, NL, EXP, and NEXP, and discuss their relationships and significance within the field of computational complexity. This introduction sets the stage for a deeper exploration of these concepts in subsequent sections, including the open question of whether P equals NP and the implications of the extended Church-Turing thesis on the definition of these classes.

Random Access Machines (RAM)

Definition

A Random Access Machine (RAM) is a computational model that, similar to the Unlimited Register Machine (URM), employs a set of registers for computation. Specifically, a RAM consists of an infinite set of registers $R_0, R_1, R_2, \dots$. Each register can be accessed in constant time, and each can store an integer of unbounded size. This feature of constant-time access to any register distinguishes the RAM from Turing machines, which have sequential memory access. This makes the RAM model more akin to the architecture of modern computers, where memory locations can be accessed directly.

Instructions

The RAM model is equipped with a rich instruction set, which includes, but is not limited to, the following operations:

add J: Adds the content of register $R_J$ to the content of register $R_0$, i.e., $R_0 \leftarrow R_0 + R_J$.
add immediate J: Adds the constant value $J$ to the content of register $R_0$, i.e., $R_0 \leftarrow R_0 + J$.
add indirect J: Adds the content of the register whose address is stored in $R_J$ to the content of register $R_0$, i.e., $R_0 \leftarrow R_0 + R_{R_J}$. This is known as indirect addressing, allowing for dynamic memory access.

In addition to these arithmetic instructions, RAMs also have separate registers for storing inputs, denoted as $I_1, I_2, \dots$, and various jump instructions to control the flow of execution, enabling conditional and unconditional branching.

Turing Completeness and Simulation

The RAM model is Turing complete, meaning it can simulate any Turing machine and vice versa. This equivalence underscores the universality of these models. The following simulation results are particularly noteworthy for understanding the time overhead involved in translating between these models:

Turing Machine to RAM: A Turing machine operating in time $f(n)$ can be simulated by a RAM in time $O(f(n))$. This result is not surprising, given the RAM’s rich instruction set and random access capabilities, which allow it to perform operations more directly than a Turing machine.
RAM to Turing Machine: A RAM $\phi$ operating in time $f(n)$ can be simulated by a Turing machine $M$ in time $O(f(n)^3)$. This result is more significant, as it demonstrates that the sequential access of a Turing machine only incurs a cubic time overhead compared to the random access of a RAM. The cubic factor arises from the need for the Turing machine to simulate random access by traversing the tape, which is a less efficient process.

Remark: The simulation of a RAM by a Turing machine is interesting because it shows that the sequential access of a Turing machine only results in a cubic time loss compared to the random access of a RAM. This result is closely related to the extended Church-Turing thesis and the use of uniform cost criteria. The cubic overhead indicates that the operations a RAM can perform do not drastically increase the size of the input, thus justifying the use of a uniform cost criterion. This is because the size of the integers stored in the registers grows slowly.

Note: The crucial aspect of the RAM simulation is that the ‘add’ operation increases the size of the integers by at most one bit at each step. This limitation is essential for achieving the $O(f(n)^3)$ simulation time by a Turing machine. If operations like multiplication were allowed, the size of the integers could grow exponentially, requiring a logarithmic cost criterion instead of a uniform one. This is because multiplication can double the size of the numbers involved in a single step, which would lead to a much larger time overhead when simulated on a Turing machine.

Non-deterministic Turing Machines

Definition

A non-deterministic Turing machine (NDTM) is a generalization of the standard deterministic Turing machine (DTM). Like a DTM, an NDTM is defined by a tuple consisting of:

A finite set of states $Q$.
A finite alphabet $\Gamma$.
A transition relation $\Delta$.
A starting state $q_0 \in Q$.

The key difference between an NDTM and a DTM lies in the transition mechanism. In a DTM, the transition function $\delta$ maps a state and the current tape symbols to a unique next state, new tape symbols, and head movements. In contrast, an NDTM replaces this transition function with a transition relation $\Delta$. This relation is a subset of: \[Q \times \Gamma^k \times (Q \cup \{\text{yes, no, halt}\}) \times \Gamma^k \times \{L, R, S\}^k\] where $k$ is the number of tapes. This means that for a given state and tape symbols, there can be multiple possible next states, tape symbols, and head movements, or none at all. The non-deterministic nature arises from the possibility of having multiple choices for the next step, allowing the machine to explore different computational paths simultaneously.

Configurations

The notion of a configuration for an NDTM is identical to that of a DTM. A configuration is a snapshot of the machine’s state at a particular point in time, represented as: \[(q, w_1u_1, w_2u_2, \dots, w_ku_k)\] where $q$ is the current state, and $w_i u_i$ represents the content of the $i$-th tape, with $w_i$ being the portion of the tape to the left of the head and $u_i$ being the portion starting from the head’s position, including the symbol currently being read. The significant difference is that, due to the transition relation, an NDTM can have multiple possible next configurations from a single current configuration, unlike a DTM which has only one. This branching behavior is what allows NDTMs to explore multiple computational paths concurrently.

Computation

Given an input $x$, an NDTM can follow multiple computation paths. Starting from the initial configuration, the machine non-deterministically chooses one of the possible transitions at each step. This results in a tree-like structure of possible computations, where each branch represents a different sequence of choices. Each computation path eventually terminates in one of the following states: ‘yes’, ‘no’, or ‘halt’. The ‘halt’ state is not relevant for decision problems, where the machine must explicitly accept or reject. The key idea is that the NDTM explores all possible computation paths simultaneously, in a conceptual sense, rather than sequentially.

Acceptance

The acceptance criterion for an NDTM is fundamentally different from that of a DTM. A language $L$ is decided (or accepted) by an NDTM $N$ if the following conditions are met:

Acceptance Condition: If an input $x$ belongs to the language $L$ ($x \in L$), then there exists at least one computation path of $N$ on input $x$ that terminates in the ‘yes’ state. This means that if the input is in the language, at least one possible sequence of non-deterministic choices will lead to acceptance.
Rejection Condition: If an input $x$ does not belong to the language $L$ ($x \notin L$), then all computation paths of $N$ on input $x$ terminate in the ‘no’ state. This means that if the input is not in the language, no matter what choices the NDTM makes, it will always end up rejecting the input.

This means that an NDTM accepts an input if at least one of its computation paths leads to acceptance, while it rejects an input only if all possible computation paths lead to rejection. This asymmetric acceptance criterion is a key feature of non-deterministic computation.

Reachability Problem

Problem Definition

The reachability problem is a fundamental problem in graph theory. Given a directed graph $G = (V, E)$, where $V$ is the set of vertices (nodes) and $E$ is the set of directed edges, and two specific nodes $u, v \in V$, the problem asks to determine whether there exists a path from node $u$ to node $v$ in $G$. A path is a sequence of nodes connected by edges in the graph, where each edge points from one node to the next in the sequence.

Deterministic Solution

The reachability problem can be solved using standard graph traversal algorithms such as Breadth-First Search (BFS) or Depth-First Search (DFS). These algorithms systematically explore the graph to find a path from the source node $u$ to the target node $v$.

Time Complexity: In a standard model of computation (e.g., using adjacency lists), both BFS and DFS have a time complexity of $O(|V| + |E|)$, where $|V|$ is the number of vertices and $|E|$ is the number of edges. This is because, in the worst case, they may need to visit all nodes and edges in the graph. When implemented on a Turing machine, the time complexity remains polynomial, although it may be higher than linear due to the overhead of simulating random access memory. The polynomial time complexity is a consequence of the extended Church-Turing thesis, which states that any reasonable model of computation can be simulated by a Turing machine with at most polynomial overhead.
Space Complexity: In a standard model of computation, both BFS and DFS require $O(|V|)$ space in the worst case. For BFS, this is primarily for storing the queue of nodes to visit, and for DFS, it is for storing the call stack and the visited nodes. On a Turing machine, the space complexity is also polynomial, as the Turing machine needs to store the queue, the stack, and the visited nodes on its tapes.

Open Question: A key question is whether the reachability problem can be solved by a deterministic Turing machine using only logarithmic space, i.e., $O(\log n)$, where $n$ is the size of the input (the encoding of the graph). This is a challenging open problem in complexity theory, as it would imply that reachability is in the complexity class L (Logarithmic space).

Non-deterministic Solution

A non-deterministic Turing machine can solve the reachability problem more space-efficiently by "guessing" a path from $u$ to $v$. The algorithm proceeds as follows:

$current\_node \gets u$ $counter \gets 0$ Non-deterministically generate a node $next\_node$ if edge $(current\_node, next\_node)$ does not exist then return ‘no’ $current\_node \gets next\_node$ if $current\_node = v$ then return ‘yes’ $counter \gets counter + 1$ if $counter = |V|$ then return ‘no’

Space Complexity: The space required by this non-deterministic algorithm is dominated by the storage of the current node, the next node, and the counter. Since each node can be represented using $\log |V|$ bits, and the counter also requires $\log |V|$ bits, the overall space complexity is $O(\log |V|)$, which is $O(\log n)$, where $n$ is the size of the input (the encoding of the graph). This logarithmic space complexity demonstrates the power of non-determinism in reducing space requirements.

Open Question: What is the deterministic space complexity of the reachability problem? Can we design a deterministic algorithm that uses logarithmic space, or something close to it? This remains an important open question in the field of computational complexity, and it is related to the question of whether the complexity class L is equal to NL.

Complexity Classes

Time Complexity

We define the following complexity classes based on the time required by Turing machines to decide languages:

$\text{TIME}(f(n))$: This class contains all languages that can be decided by a deterministic Turing machine in time $O(f(n))$, where $n$ is the size of the input. This means that for any language in this class, there exists a deterministic Turing machine that can decide whether a given input string belongs to the language in at most $c \cdot f(n)$ steps, for some constant $c$.
$\text{NTIME}(f(n))$: This class contains all languages that can be decided by a non-deterministic Turing machine in time $O(f(n))$, where $n$ is the size of the input. Similarly, this means that there exists a non-deterministic Turing machine that can decide whether an input string belongs to the language in at most $c \cdot f(n)$ steps, for some constant $c$, along at least one computation path.

Space Complexity

Similarly, we define complexity classes based on the space (memory) used by Turing machines:

$\text{SPACE}(f(n))$: This class contains all languages that can be decided by a deterministic Turing machine using space $O(f(n))$, where $n$ is the size of the input. This means that the deterministic Turing machine uses at most $c \cdot f(n)$ cells on its work tapes, for some constant $c$.
$\text{NSPACE}(f(n))$: This class contains all languages that can be decided by a non-deterministic Turing machine using space $O(f(n))$, where $n$ is the size of the input. This means that the non-deterministic Turing machine uses at most $c \cdot f(n)$ cells on its work tapes, for some constant $c$, across all computation paths.

Important Complexity Classes

Based on the above definitions, we introduce several important complexity classes that are frequently studied in computational complexity theory:

P (Polynomial Time): $\text{P} = \bigcup_{h \in \mathbb{N}} \text{TIME}(n^h)$. This class contains all languages that can be decided by a deterministic Turing machine in polynomial time. In other words, there exists a deterministic Turing machine that can decide membership in the language in time $O(n^h)$ for some constant $h$.
NP (Non-deterministic Polynomial Time): $\text{NP} = \bigcup_{h \in \mathbb{N}} \text{NTIME}(n^h)$. This class contains all languages that can be decided by a non-deterministic Turing machine in polynomial time. This means that there exists a non-deterministic Turing machine that can decide membership in the language in time $O(n^h)$ for some constant $h$, along at least one computation path.
PSPACE (Polynomial Space): $\text{PSPACE} = \bigcup_{h \in \mathbb{N}} \text{SPACE}(n^h)$. This class contains all languages that can be decided by a deterministic Turing machine using polynomial space. The deterministic Turing machine uses at most $O(n^h)$ space for some constant $h$.
NPSPACE (Non-deterministic Polynomial Space): $\text{NPSPACE} = \bigcup_{h \in \mathbb{N}} \text{NSPACE}(n^h)$. This class contains all languages that can be decided by a non-deterministic Turing machine using polynomial space. The non-deterministic Turing machine uses at most $O(n^h)$ space for some constant $h$, across all computation paths.
L (Logarithmic Space): $\text{L} = \text{SPACE}(\log n)$. This class contains all languages that can be decided by a deterministic Turing machine using logarithmic space. The deterministic Turing machine uses at most $O(\log n)$ space on its work tapes.
NL (Non-deterministic Logarithmic Space): $\text{NL} = \text{NSPACE}(\log n)$. This class contains all languages that can be decided by a non-deterministic Turing machine using logarithmic space. The non-deterministic Turing machine uses at most $O(\log n)$ space on its work tapes, across all computation paths.
EXP (Exponential Time): $\text{EXP} = \bigcup_{h \in \mathbb{N}} \text{TIME}(2^{n^h})$. This class contains all languages that can be decided by a deterministic Turing machine in exponential time. There exists a deterministic Turing machine that can decide membership in the language in time $O(2^{n^h})$ for some constant $h$.
NEXP (Non-deterministic Exponential Time): $\text{NEXP} = \bigcup_{h \in \mathbb{N}} \text{NTIME}(2^{n^h})$. This class contains all languages that can be decided by a non-deterministic Turing machine in exponential time. There exists a non-deterministic Turing machine that can decide membership in the language in time $O(2^{n^h})$ for some constant $h$, along at least one computation path.

Inclusions

The relationships between these complexity classes are described by the following inclusions, which represent the known hierarchy of these classes:

$\text{P} \subseteq \text{NP}$. This inclusion is straightforward since any deterministic Turing machine is also a special case of a non-deterministic Turing machine. The question of whether $\text{P} = \text{NP}$ is one of the most famous open problems in computer science and has profound implications for the limits of computation.
$\text{L} \subseteq \text{NL} \subseteq \text{P} \subseteq \text{NP} \subseteq \text{PSPACE} = \text{NPSPACE} \subseteq \text{EXP} \subseteq \text{NEXP}$. This chain of inclusions represents the known relationships between these classes. Each inclusion means that every language in the class on the left is also in the class on the right.

Note: The equality $\text{PSPACE} = \text{NPSPACE}$ is a significant result that will be proven later in the course. It demonstrates that, unlike time complexity, non-determinism does not provide an advantage in terms of space complexity at the polynomial level. This result is a consequence of Savitch’s theorem.

Polynomial Hierarchy

There is an infinite hierarchy of complexity classes between NP and PSPACE, known as the polynomial hierarchy (PH). This hierarchy provides a finer-grained classification of problems within this range, and it is defined using alternating quantifiers over polynomial-time predicates.

Elementary Class

The union of EXP, 2-EXP (double exponential time), 3-EXP (triple exponential time), and so on, is called the elementary class. This class encompasses problems that can be solved with a tower of exponentials, where the height of the tower is a fixed constant.

Tractability

In the context of complexity theory, we often use the following terms to distinguish between problems that can be solved efficiently and those that are likely to be intractable:

Tractable: Problems that belong to the class P are considered tractable, meaning they can be solved efficiently in polynomial time. This is because polynomial time algorithms are generally considered to be practical for reasonably sized inputs.
Intractable: Problems that lie outside the class P are considered intractable, meaning they are likely to require an impractical amount of time to solve as the input size increases. This is because exponential time algorithms can quickly become infeasible for even moderately sized inputs.

Remark: The importance of the class P stems from the extended Church-Turing thesis, which suggests that the class P is invariant across reasonable models of computation. This means that if a problem can be solved in polynomial time on one model of computation, it can also be solved in polynomial time on other models, making P a robust and fundamental class. This invariance makes P a natural class to represent the set of problems that are considered efficiently solvable.

Conclusion

This lecture provided a comprehensive introduction to non-deterministic Turing machines (NDTMs) and contrasted them with deterministic Turing machines (DTMs), emphasizing the fundamental differences in their transition mechanisms and computational capabilities. We explored the reachability problem as a key example, illustrating how non-determinism can lead to more space-efficient solutions compared to deterministic approaches, particularly in the context of logarithmic space. We also defined several fundamental complexity classes, including P, NP, PSPACE, NPSPACE, L, NL, EXP, and NEXP, and discussed their relationships and inclusions, highlighting the known hierarchy of these classes. The lecture emphasized the significance of the P versus NP problem as a major open question in computer science and the role of the extended Church-Turing thesis in understanding the robustness of these complexity classes across different models of computation.

Follow-up Questions:

Reachability in Logarithmic Space: Can the reachability problem be solved deterministically using logarithmic space? If not, how close can we get to this bound? This question highlights the gap between deterministic and non-deterministic space complexity and motivates the study of the complexity class L versus NL.
Implications of P = NP: What are the theoretical and practical implications if the complexity classes P and NP were proven to be equal? This is a central open question in computer science with profound consequences, as it would imply that every problem whose solution can be quickly verified can also be solved quickly.
Polynomial Hierarchy: How does the polynomial hierarchy (PH) relate to the known complexity classes, and what does it tell us about the structure of problems between NP and PSPACE? This question motivates the study of finer-grained complexity classes beyond NP and PSPACE.
Examples of Problems: What are some concrete examples of problems that belong to each of the complexity classes discussed, and how do these examples help us understand the nature of these classes? This question emphasizes the practical relevance of these theoretical concepts.

Next Lecture: In the next lecture, we will delve deeper into the relationships between these complexity classes. We will explore further results, including the proof that PSPACE = NPSPACE, and we will discuss the polynomial hierarchy in more detail. We will also examine specific examples of problems within these classes to solidify our understanding of their properties and implications, and we will further discuss the implications of the extended Church-Turing thesis.

Extended Church-Turing Thesis

The extended Church-Turing thesis suggests that all reasonable models of computation can be simulated by a Turing machine with at most a polynomial slowdown. This thesis is crucial for the robustness of complexity classes like P, as it implies that the class of problems solvable in polynomial time is invariant under different computational models. This invariance makes the class P a natural and fundamental class for defining the set of problems that are considered efficiently solvable.

--- title: "Lecture Notes: Non-deterministic Turing Machines and Complexity Classes" 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 {#sec:introduction} This lecture introduces the concept of non-deterministic Turing machines and explores their relationship to deterministic Turing machines. We will also define and discuss several important complexity classes. The lecture begins with a discussion of the Random Access Machine (RAM) model, highlighting its similarities and differences with Turing machines, particularly in terms of memory access and instruction sets. We then formally define non-deterministic Turing machines (NDTMs), contrasting them with their deterministic counterparts by focusing on the transition relation versus the transition function. The reachability problem is introduced as a practical example to illustrate the differences in computational power and space requirements between deterministic and non-deterministic models. Finally, we define key complexity classes such as P, NP, PSPACE, NPSPACE, L, NL, EXP, and NEXP, and discuss their relationships and significance within the field of computational complexity. This introduction sets the stage for a deeper exploration of these concepts in subsequent sections, including the open question of whether P equals NP and the implications of the extended Church-Turing thesis on the definition of these classes. # Random Access Machines (RAM) {#sec:ram} ## Definition {#subsec:ram_definition} ::: tcolorbox A Random Access Machine (RAM) is a computational model that, similar to the Unlimited Register Machine (URM), employs a set of registers for computation. Specifically, a RAM consists of an infinite set of registers $R_0, R_1, R_2, \dots$. Each register can be accessed in constant time, and each can store an integer of unbounded size. This feature of constant-time access to any register distinguishes the RAM from Turing machines, which have sequential memory access. This makes the RAM model more akin to the architecture of modern computers, where memory locations can be accessed directly. ::: ## Instructions {#subsec:ram_instructions} The RAM model is equipped with a rich instruction set, which includes, but is not limited to, the following operations: - **add J**: Adds the content of register $R_J$ to the content of register $R_0$, i.e., $R_0 \leftarrow R_0 + R_J$. - **add immediate J**: Adds the constant value $J$ to the content of register $R_0$, i.e., $R_0 \leftarrow R_0 + J$. - **add indirect J**: Adds the content of the register whose address is stored in $R_J$ to the content of register $R_0$, i.e., $R_0 \leftarrow R_0 + R_{R_J}$. This is known as indirect addressing, allowing for dynamic memory access. In addition to these arithmetic instructions, RAMs also have separate registers for storing inputs, denoted as $I_1, I_2, \dots$, and various jump instructions to control the flow of execution, enabling conditional and unconditional branching. ## Turing Completeness and Simulation {#subsec:ram_simulation} The RAM model is Turing complete, meaning it can simulate any Turing machine and vice versa. This equivalence underscores the universality of these models. The following simulation results are particularly noteworthy for understanding the time overhead involved in translating between these models: - **Turing Machine to RAM**: A Turing machine operating in time $f(n)$ can be simulated by a RAM in time $O(f(n))$. This result is not surprising, given the RAM's rich instruction set and random access capabilities, which allow it to perform operations more directly than a Turing machine. - **RAM to Turing Machine**: A RAM $\phi$ operating in time $f(n)$ can be simulated by a Turing machine $M$ in time $O(f(n)^3)$. This result is more significant, as it demonstrates that the sequential access of a Turing machine only incurs a cubic time overhead compared to the random access of a RAM. The cubic factor arises from the need for the Turing machine to simulate random access by traversing the tape, which is a less efficient process. ::: tcolorbox **Remark:** The simulation of a RAM by a Turing machine is interesting because it shows that the sequential access of a Turing machine only results in a cubic time loss compared to the random access of a RAM. This result is closely related to the [extended Church-Turing thesis](#sec:extended_church_thesis) and the use of uniform cost criteria. The cubic overhead indicates that the operations a RAM can perform do not drastically increase the size of the input, thus justifying the use of a uniform cost criterion. This is because the size of the integers stored in the registers grows slowly. ::: ::: tcolorbox **Note:** The crucial aspect of the RAM simulation is that the 'add' operation increases the size of the integers by at most one bit at each step. This limitation is essential for achieving the $O(f(n)^3)$ simulation time by a Turing machine. If operations like multiplication were allowed, the size of the integers could grow exponentially, requiring a logarithmic cost criterion instead of a uniform one. This is because multiplication can double the size of the numbers involved in a single step, which would lead to a much larger time overhead when simulated on a Turing machine. ::: # Non-deterministic Turing Machines {#sec:nondeterministic_turing_machines} ## Definition {#subsec:ndtm_definition} ::: tcolorbox A non-deterministic Turing machine (NDTM) is a generalization of the standard deterministic Turing machine (DTM). Like a DTM, an NDTM is defined by a tuple consisting of: - A finite set of states $Q$. - A finite alphabet $\Gamma$. - A transition relation $\Delta$. - A starting state $q_0 \in Q$. The key difference between an NDTM and a DTM lies in the transition mechanism. In a DTM, the transition function $\delta$ maps a state and the current tape symbols to a unique next state, new tape symbols, and head movements. In contrast, an NDTM replaces this transition function with a transition relation $\Delta$. This relation is a subset of: $$Q \times \Gamma^k \times (Q \cup \{\text{yes, no, halt}\}) \times \Gamma^k \times \{L, R, S\}^k$$ where $k$ is the number of tapes. This means that for a given state and tape symbols, there can be multiple possible next states, tape symbols, and head movements, or none at all. The non-deterministic nature arises from the possibility of having multiple choices for the next step, allowing the machine to explore different computational paths simultaneously. ::: ## Configurations {#subsec:ndtm_configurations} The notion of a configuration for an NDTM is identical to that of a DTM. A configuration is a snapshot of the machine's state at a particular point in time, represented as: $$(q, w_1u_1, w_2u_2, \dots, w_ku_k)$$ where $q$ is the current state, and $w_i u_i$ represents the content of the $i$-th tape, with $w_i$ being the portion of the tape to the left of the head and $u_i$ being the portion starting from the head's position, including the symbol currently being read. The significant difference is that, due to the transition relation, an NDTM can have multiple possible next configurations from a single current configuration, unlike a DTM which has only one. This branching behavior is what allows NDTMs to explore multiple computational paths concurrently. ## Computation {#subsec:ndtm_computation} Given an input $x$, an NDTM can follow multiple computation paths. Starting from the initial configuration, the machine non-deterministically chooses one of the possible transitions at each step. This results in a tree-like structure of possible computations, where each branch represents a different sequence of choices. Each computation path eventually terminates in one of the following states: 'yes', 'no', or 'halt'. The 'halt' state is not relevant for decision problems, where the machine must explicitly accept or reject. The key idea is that the NDTM explores all possible computation paths simultaneously, in a conceptual sense, rather than sequentially. ## Acceptance {#subsec:ndtm_acceptance} ::: tcolorbox The acceptance criterion for an NDTM is fundamentally different from that of a DTM. A language $L$ is decided (or accepted) by an NDTM $N$ if the following conditions are met: - **Acceptance Condition:** If an input $x$ belongs to the language $L$ ($x \in L$), then *there exists at least one* computation path of $N$ on input $x$ that terminates in the 'yes' state. This means that if the input is in the language, at least one possible sequence of non-deterministic choices will lead to acceptance. - **Rejection Condition:** If an input $x$ does not belong to the language $L$ ($x \notin L$), then *all* computation paths of $N$ on input $x$ terminate in the 'no' state. This means that if the input is not in the language, no matter what choices the NDTM makes, it will always end up rejecting the input. This means that an NDTM accepts an input if at least one of its computation paths leads to acceptance, while it rejects an input only if all possible computation paths lead to rejection. This asymmetric acceptance criterion is a key feature of non-deterministic computation. ::: # Reachability Problem {#sec:reachability_problem} ## Problem Definition {#subsec:reachability_definition} ::: tcolorbox The reachability problem is a fundamental problem in graph theory. Given a directed graph $G = (V, E)$, where $V$ is the set of vertices (nodes) and $E$ is the set of directed edges, and two specific nodes $u, v \in V$, the problem asks to determine whether there exists a path from node $u$ to node $v$ in $G$. A path is a sequence of nodes connected by edges in the graph, where each edge points from one node to the next in the sequence. ::: ## Deterministic Solution {#subsec:reachability_deterministic} The reachability problem can be solved using standard graph traversal algorithms such as Breadth-First Search (BFS) or Depth-First Search (DFS). These algorithms systematically explore the graph to find a path from the source node $u$ to the target node $v$. - **Time Complexity:** In a standard model of computation (e.g., using adjacency lists), both BFS and DFS have a time complexity of $O(|V| + |E|)$, where $|V|$ is the number of vertices and $|E|$ is the number of edges. This is because, in the worst case, they may need to visit all nodes and edges in the graph. When implemented on a Turing machine, the time complexity remains polynomial, although it may be higher than linear due to the overhead of simulating random access memory. The polynomial time complexity is a consequence of the extended Church-Turing thesis, which states that any reasonable model of computation can be simulated by a Turing machine with at most polynomial overhead. - **Space Complexity:** In a standard model of computation, both BFS and DFS require $O(|V|)$ space in the worst case. For BFS, this is primarily for storing the queue of nodes to visit, and for DFS, it is for storing the call stack and the visited nodes. On a Turing machine, the space complexity is also polynomial, as the Turing machine needs to store the queue, the stack, and the visited nodes on its tapes. ::: tcolorbox **Open Question:** A key question is whether the reachability problem can be solved by a deterministic Turing machine using only logarithmic space, i.e., $O(\log n)$, where $n$ is the size of the input (the encoding of the graph). This is a challenging open problem in complexity theory, as it would imply that reachability is in the complexity class L (Logarithmic space). ::: ## Non-deterministic Solution {#subsec:reachability_nondeterministic} A non-deterministic Turing machine can solve the reachability problem more space-efficiently by \"guessing\" a path from $u$ to $v$. The algorithm proceeds as follows: :::: algorithm ::: algorithmic $current\_node \gets u$ $counter \gets 0$ **Non-deterministically** generate a node $next\_node$ **if** edge $(current\_node, next\_node)$ does not exist **then** **return** 'no' $current\_node \gets next\_node$ **if** $current\_node = v$ **then** **return** 'yes' $counter \gets counter + 1$ **if** $counter = |V|$ **then** **return** 'no' ::: :::: **Space Complexity:** The space required by this non-deterministic algorithm is dominated by the storage of the current node, the next node, and the counter. Since each node can be represented using $\log |V|$ bits, and the counter also requires $\log |V|$ bits, the overall space complexity is $O(\log |V|)$, which is $O(\log n)$, where $n$ is the size of the input (the encoding of the graph). This logarithmic space complexity demonstrates the power of non-determinism in reducing space requirements. ::: tcolorbox **Open Question:** What is the deterministic space complexity of the reachability problem? Can we design a deterministic algorithm that uses logarithmic space, or something close to it? This remains an important open question in the field of computational complexity, and it is related to the question of whether the complexity class L is equal to NL. ::: # Complexity Classes {#sec:complexity_classes} ## Time Complexity {#subsec:time_complexity} We define the following complexity classes based on the time required by Turing machines to decide languages: - $\text{TIME}(f(n))$: This class contains all languages that can be decided by a deterministic Turing machine in time $O(f(n))$, where $n$ is the size of the input. This means that for any language in this class, there exists a deterministic Turing machine that can decide whether a given input string belongs to the language in at most $c \cdot f(n)$ steps, for some constant $c$. - $\text{NTIME}(f(n))$: This class contains all languages that can be decided by a non-deterministic Turing machine in time $O(f(n))$, where $n$ is the size of the input. Similarly, this means that there exists a non-deterministic Turing machine that can decide whether an input string belongs to the language in at most $c \cdot f(n)$ steps, for some constant $c$, along at least one computation path. ## Space Complexity {#subsec:space_complexity} Similarly, we define complexity classes based on the space (memory) used by Turing machines: - $\text{SPACE}(f(n))$: This class contains all languages that can be decided by a deterministic Turing machine using space $O(f(n))$, where $n$ is the size of the input. This means that the deterministic Turing machine uses at most $c \cdot f(n)$ cells on its work tapes, for some constant $c$. - $\text{NSPACE}(f(n))$: This class contains all languages that can be decided by a non-deterministic Turing machine using space $O(f(n))$, where $n$ is the size of the input. This means that the non-deterministic Turing machine uses at most $c \cdot f(n)$ cells on its work tapes, for some constant $c$, across all computation paths. ## Important Complexity Classes {#subsec:important_complexity_classes} Based on the above definitions, we introduce several important complexity classes that are frequently studied in computational complexity theory: - **P (Polynomial Time):** $\text{P} = \bigcup_{h \in \mathbb{N}} \text{TIME}(n^h)$. This class contains all languages that can be decided by a deterministic Turing machine in polynomial time. In other words, there exists a deterministic Turing machine that can decide membership in the language in time $O(n^h)$ for some constant $h$. - **NP (Non-deterministic Polynomial Time):** $\text{NP} = \bigcup_{h \in \mathbb{N}} \text{NTIME}(n^h)$. This class contains all languages that can be decided by a non-deterministic Turing machine in polynomial time. This means that there exists a non-deterministic Turing machine that can decide membership in the language in time $O(n^h)$ for some constant $h$, along at least one computation path. - **PSPACE (Polynomial Space):** $\text{PSPACE} = \bigcup_{h \in \mathbb{N}} \text{SPACE}(n^h)$. This class contains all languages that can be decided by a deterministic Turing machine using polynomial space. The deterministic Turing machine uses at most $O(n^h)$ space for some constant $h$. - **NPSPACE (Non-deterministic Polynomial Space):** $\text{NPSPACE} = \bigcup_{h \in \mathbb{N}} \text{NSPACE}(n^h)$. This class contains all languages that can be decided by a non-deterministic Turing machine using polynomial space. The non-deterministic Turing machine uses at most $O(n^h)$ space for some constant $h$, across all computation paths. - **L (Logarithmic Space):** $\text{L} = \text{SPACE}(\log n)$. This class contains all languages that can be decided by a deterministic Turing machine using logarithmic space. The deterministic Turing machine uses at most $O(\log n)$ space on its work tapes. - **NL (Non-deterministic Logarithmic Space):** $\text{NL} = \text{NSPACE}(\log n)$. This class contains all languages that can be decided by a non-deterministic Turing machine using logarithmic space. The non-deterministic Turing machine uses at most $O(\log n)$ space on its work tapes, across all computation paths. - **EXP (Exponential Time):** $\text{EXP} = \bigcup_{h \in \mathbb{N}} \text{TIME}(2^{n^h})$. This class contains all languages that can be decided by a deterministic Turing machine in exponential time. There exists a deterministic Turing machine that can decide membership in the language in time $O(2^{n^h})$ for some constant $h$. - **NEXP (Non-deterministic Exponential Time):** $\text{NEXP} = \bigcup_{h \in \mathbb{N}} \text{NTIME}(2^{n^h})$. This class contains all languages that can be decided by a non-deterministic Turing machine in exponential time. There exists a non-deterministic Turing machine that can decide membership in the language in time $O(2^{n^h})$ for some constant $h$, along at least one computation path. ## Inclusions {#subsec:inclusions} The relationships between these complexity classes are described by the following inclusions, which represent the known hierarchy of these classes: - $\text{P} \subseteq \text{NP}$. This inclusion is straightforward since any deterministic Turing machine is also a special case of a non-deterministic Turing machine. The question of whether $\text{P} = \text{NP}$ is one of the most famous open problems in computer science and has profound implications for the limits of computation. - $\text{L} \subseteq \text{NL} \subseteq \text{P} \subseteq \text{NP} \subseteq \text{PSPACE} = \text{NPSPACE} \subseteq \text{EXP} \subseteq \text{NEXP}$. This chain of inclusions represents the known relationships between these classes. Each inclusion means that every language in the class on the left is also in the class on the right. ::: tcolorbox **Note:** The equality $\text{PSPACE} = \text{NPSPACE}$ is a significant result that will be proven later in the course. It demonstrates that, unlike time complexity, non-determinism does not provide an advantage in terms of space complexity at the polynomial level. This result is a consequence of Savitch's theorem. ::: ## Polynomial Hierarchy {#subsec:polynomial_hierarchy} There is an infinite hierarchy of complexity classes between NP and PSPACE, known as the polynomial hierarchy (PH). This hierarchy provides a finer-grained classification of problems within this range, and it is defined using alternating quantifiers over polynomial-time predicates. ## Elementary Class {#subsec:elementary_class} The union of EXP, 2-EXP (double exponential time), 3-EXP (triple exponential time), and so on, is called the elementary class. This class encompasses problems that can be solved with a tower of exponentials, where the height of the tower is a fixed constant. ## Tractability {#subsec:tractability} In the context of complexity theory, we often use the following terms to distinguish between problems that can be solved efficiently and those that are likely to be intractable: - **Tractable:** Problems that belong to the class P are considered tractable, meaning they can be solved efficiently in polynomial time. This is because polynomial time algorithms are generally considered to be practical for reasonably sized inputs. - **Intractable:** Problems that lie outside the class P are considered intractable, meaning they are likely to require an impractical amount of time to solve as the input size increases. This is because exponential time algorithms can quickly become infeasible for even moderately sized inputs. ::: tcolorbox **Remark:** The importance of the class P stems from the [extended Church-Turing thesis](#sec:extended_church_thesis), which suggests that the class P is invariant across reasonable models of computation. This means that if a problem can be solved in polynomial time on one model of computation, it can also be solved in polynomial time on other models, making P a robust and fundamental class. This invariance makes P a natural class to represent the set of problems that are considered efficiently solvable. ::: # Conclusion {#sec:conclusion} This lecture provided a comprehensive introduction to non-deterministic Turing machines (NDTMs) and contrasted them with deterministic Turing machines (DTMs), emphasizing the fundamental differences in their transition mechanisms and computational capabilities. We explored the reachability problem as a key example, illustrating how non-determinism can lead to more space-efficient solutions compared to deterministic approaches, particularly in the context of logarithmic space. We also defined several fundamental complexity classes, including P, NP, PSPACE, NPSPACE, L, NL, EXP, and NEXP, and discussed their relationships and inclusions, highlighting the known hierarchy of these classes. The lecture emphasized the significance of the P versus NP problem as a major open question in computer science and the role of the extended Church-Turing thesis in understanding the robustness of these complexity classes across different models of computation. ::: tcolorbox **Follow-up Questions:** 1. **Reachability in Logarithmic Space:** Can the reachability problem be solved deterministically using logarithmic space? If not, how close can we get to this bound? This question highlights the gap between deterministic and non-deterministic space complexity and motivates the study of the complexity class L versus NL. 2. **Implications of P = NP:** What are the theoretical and practical implications if the complexity classes P and NP were proven to be equal? This is a central open question in computer science with profound consequences, as it would imply that every problem whose solution can be quickly verified can also be solved quickly. 3. **Polynomial Hierarchy:** How does the polynomial hierarchy (PH) relate to the known complexity classes, and what does it tell us about the structure of problems between NP and PSPACE? This question motivates the study of finer-grained complexity classes beyond NP and PSPACE. 4. **Examples of Problems:** What are some concrete examples of problems that belong to each of the complexity classes discussed, and how do these examples help us understand the nature of these classes? This question emphasizes the practical relevance of these theoretical concepts. ::: **Next Lecture:** In the next lecture, we will delve deeper into the relationships between these complexity classes. We will explore further results, including the proof that PSPACE = NPSPACE, and we will discuss the polynomial hierarchy in more detail. We will also examine specific examples of problems within these classes to solidify our understanding of their properties and implications, and we will further discuss the implications of the extended Church-Turing thesis. ## Extended Church-Turing Thesis {#sec:extended_church_thesis .unnumbered} The extended Church-Turing thesis suggests that all reasonable models of computation can be simulated by a Turing machine with at most a polynomial slowdown. This thesis is crucial for the robustness of complexity classes like P, as it implies that the class of problems solvable in polynomial time is invariant under different computational models. This invariance makes the class P a natural and fundamental class for defining the set of problems that are considered efficiently solvable.