Introduction to Classical Complexity Theory

Author

Your Name

Published

January 28, 2025

Introduction

This document introduces the fundamental concepts of classical complexity theory. We will primarily focus on decision problems and their classification, exploring the distinctions between decisional, functional, and optimization problems. Understanding these problem types is crucial for framing computational challenges within a rigorous theoretical context. We will then introduce computational models, specifically Turing Machines and Unlimited Register Machines (URMs), which serve as abstract machines for analyzing the complexity of algorithms. These models allow us to quantify the resources required to solve computational problems. Furthermore, we will discuss the Church-Turing thesis and its extended version, emphasizing the significance of the logarithmic cost criterion in accurate complexity analysis. This criterion is essential when dealing with operations that significantly increase the size of intermediate results during computation, as it provides a more realistic measure of computational effort. The document aims to provide a solid foundation for understanding the theoretical underpinnings of computational complexity, setting the stage for more advanced topics in the field. The content of this document is based on the book "Computational Complexity" by Christos H. Papadimitriou, which serves as the main reference for this part of the course.

Decision Problems: Problems with a yes/no answer.
Computational Models: Abstract machines (e.g., Turing Machines, URMs) for analyzing algorithm complexity.
Church-Turing Thesis: The assertion that any function computable by an algorithm can be computed by a Turing Machine.
Extended Church-Turing Thesis: The assertion that any reasonable model of computation is polynomially related to Turing Machines.
Logarithmic Cost Criterion: A method for measuring the cost of operations based on the number of bits involved.

Types of Computational Problems

Computational problems can be broadly classified into three distinct categories, each with different requirements for their solutions. These categories help in understanding the nature of the problem and the type of algorithms that might be suitable for solving them:

Decisional Problems: These problems require a binary decision, with the output being either "yes" or "no". They are concerned with determining whether a given input satisfies a specific property. The focus is on the existence of a solution rather than the solution itself. For example, determining if a given graph is Hamiltonian is a decisional problem.
Functional Problems: These problems require the computation of a specific output based on the given input. The output is not limited to a binary choice but can be any value or structure. The goal is to construct a solution. For example, finding a Hamiltonian path in a graph, if one exists, is a functional problem.
Optimization Problems: These problems involve finding the best solution among a set of feasible solutions, according to a given cost function. The goal is to minimize or maximize the cost function. The focus is on finding the optimal solution among many possibilities. For example, finding the Hamiltonian path with the minimum cost, where a cost is associated with each path, is an optimization problem.

Example: Hamiltonian Path Problem

To illustrate these categories, we will use the Hamiltonian Path Problem as a running example. This problem is well-known in graph theory and serves as a good example to differentiate the three types of problems.

A Hamiltonian path in a graph is a path that visits each vertex exactly once.

The Hamiltonian Path Problem can be formulated in each of the three categories as follows:

Decisional: Given a graph $G$, determine whether a Hamiltonian path exists in $G$. The output is a binary decision: "yes" if a Hamiltonian path exists, and "no" otherwise.
Functional: Given a graph $G$, find and output a Hamiltonian path if it exists. If no Hamiltonian path exists, the output should indicate "does not exist". The output is a specific path or a notification of its absence.
Optimization: Given a graph $G$ and a cost function defined on paths, find the Hamiltonian path with the minimum cost. This requires evaluating the cost of all possible Hamiltonian paths and selecting the one with the lowest cost. The output is the optimal path according to the cost function.

Examples of graphs with and without Hamiltonian paths. The red path indicates a Hamiltonian path in the left graph.

Figure 1 shows two example graphs. The graph on the left has a Hamiltonian path $A \to B \to C \to D$, while the graph on the right does not have a Hamiltonian path.

Decision Problems and Languages

In this course, we will primarily focus on decision problems. A decision problem can be conceptualized as a process that partitions the set of all possible inputs into two distinct subsets: those for which the answer is "yes" and those for which the answer is "no". This binary classification allows us to represent decision problems using the concept of formal languages, which provides a powerful framework for studying their complexity.

A language $L$ over an alphabet $\Sigma$ is a set of strings formed by concatenating symbols from $\Sigma$. Formally, $L \subseteq \Sigma^*$, where $\Sigma^*$ denotes the set of all possible strings over $\Sigma$. The alphabet $\Sigma$ is a finite set of symbols.

For any given decision problem, we can define a corresponding language $L$ as the set of all inputs for which the answer to the problem is "yes". This language $L$ is a subset of $\Sigma^*$, where $\Sigma$ is the alphabet used to encode the inputs. The "no" instances are implicitly represented by the complement of $L$ with respect to $\Sigma^*$, denoted as $\Sigma^* \setminus L$. Thus, studying decision problems is equivalent to studying languages.

Example: Hamiltonian Path Language

Let’s consider the Hamiltonian Path Problem again. We can define a language $L_{HP}$ that represents this problem as follows: \[L_{HP} = \{G \mid G \text{ is a graph with a Hamiltonian path}\}\] Here, $L_{HP}$ is the set of all graph encodings that represent graphs containing a Hamiltonian path. The elements of $L_{HP}$ are strings over some alphabet $\Sigma$ that, when decoded, represent graphs with a Hamiltonian path.

Encoding Graphs

To work with graphs as inputs to algorithms, we need to encode them as strings over a given alphabet. A common approach is to use binary strings, which allows for a uniform representation of various data structures. For example, a graph $G = (V, E)$ can be encoded as follows:

Let $|V| = n$ be the number of vertices in the graph.
The vertices are named $1, 2, \dots, n$.
The edges are represented as pairs $(i, j)$, where $i, j \in \{1, 2, \dots, n\}$.
A possible encoding is: $\text{bin}(n) \# \text{bin}(i_1) \# \text{bin}(j_1) \# \# \text{bin}(i_2) \# \text{bin}(j_2) \# \# \dots$, where $\text{bin}(x)$ represents the binary encoding of the integer $x$, and $(i_k, j_k)$ are the edges of the graph. The symbol $\#$ is used as a separator to distinguish between different parts of the encoding.

Example of a graph and its encoding.

Figure 2 shows an example of a graph and its corresponding encoding. The graph has 3 nodes and 3 edges. The encoding represents the number of nodes, followed by the edges.

Note: It is important to note that not all strings over the chosen alphabet will represent valid encodings of graphs. For instance, a string might not conform to the specified format or might represent a graph with invalid edge specifications. These strings that do not represent valid graph encodings are typically considered as "no" instances of the decision problem and are therefore not part of the language $L_{HP}$. It is generally assumed that checking whether a string is a valid encoding can be done efficiently (e.g., in linear time and constant space). This assumption is crucial for the subsequent analysis of computational complexity.

Computational Models

To analyze the complexity of computational problems, we need to define abstract computational models. These models provide a formal framework for describing algorithms and measuring their resource usage, such as time and space. In this course, we will primarily use Turing Machines as our standard model due to their simplicity and theoretical significance. However, we will also briefly discuss Unlimited Register Machines (URMs) to highlight potential issues and subtleties in complexity analysis when using different models, particularly concerning the cost of basic operations.

Turing Machines

A Turing Machine (TM) is a theoretical model of computation that consists of a finite-state control unit, an infinite tape divided into cells, and a read/write head that can move along the tape. The Turing Machine is a very low-level model, which makes it suitable for studying the fundamental limits of computation. Formally, a Turing Machine $M$ can be defined as a tuple $(Q, \Sigma, \delta, q_0)$, where:

$Q$ is a finite set of states, representing the internal configurations of the machine.
$\Sigma$ is a finite set of tape symbols (the alphabet), including a special blank symbol.
$\delta: Q \times \Sigma \rightarrow Q \times \Sigma \times \{L, R, S\}$ is the transition function, which dictates the machine’s behavior based on its current state and the symbol it reads. $\delta(q, a) = (q', a', d)$ means that if the machine is in state $q$ and reads symbol $a$, it transitions to state $q'$, writes symbol $a'$ on the tape, and moves the head according to $d$, where $L$ means move left, $R$ means move right, and $S$ means stay in the same position.
$q_0 \in Q$ is the initial state, where the machine starts its computation.

The machine operates by reading the symbol in the current cell, applying the transition function to determine the next state, writing a new symbol in the cell, and moving the head left, right, or staying in the same position. The computation continues until the machine reaches a halting state, which is a state where no transition is defined for the current symbol.

Unlimited Register Machines (URMs)

An Unlimited Register Machine (URM) is another model of computation that uses an infinite set of registers, $R_0, R_1, R_2, \dots$, each capable of storing an arbitrarily large non-negative integer. The URM operates by executing a sequence of instructions that manipulate the contents of these registers. Unlike Turing Machines, URMs operate on integers directly, which can sometimes lead to more concise programs for certain problems.

The basic instructions of a URM are:

$S_i$: Increment the content of register $R_i$ by 1 (i.e., $R_i \leftarrow R_i + 1$).
$Z_i$: Set the content of register $R_i$ to 0 (i.e., $R_i \leftarrow 0$).
$T_{i,j}$: Transfer the content of register $R_i$ to register $R_j$ (i.e., $R_j \leftarrow R_i$).
$J_{i,j,u}$: Jump to instruction $u$ if the content of register $R_i$ is equal to the content of register $R_j$. Otherwise, proceed to the next instruction in sequence. This instruction allows for conditional execution and looping.

A URM program is a finite sequence of these instructions. The input to the program is typically placed in register $R_0$ (and possibly other registers), and the output is found in register $R_0$ upon termination. The program terminates when it attempts to jump to a non-existent instruction.

Example: Deciding Equality of Two Numbers

To illustrate the differences in complexity analysis between Turing Machines and URMs, let’s consider the problem of deciding whether two given numbers are equal. This example demonstrates how different computational models can lead to different complexity results for the same problem.

Problem: Given two non-negative integers, $x$ in register $R_0$ and $y$ in register $R_1$, decide if $x = y$. The output should be 1 in $R_0$ if $x=y$ and 0 otherwise.

URM Program: The following URM program solves the equality problem:

$J_{0,1,4}$ (If $R_0 = R_1$, jump to instruction 4)
$Z_0$ (Set $R_0$ to 0)
$J_{0,0,100}$ (Jump to instruction 100, which terminates the program)
$Z_0$ (Set $R_0$ to 0)
$S_0$ (Increment $R_0$ by 1)
$J_{0,0,100}$ (Jump to instruction 100, which terminates the program)

This URM program has a constant time complexity, as it executes a fixed number of instructions (at most 6) regardless of the input values. Specifically, it executes at most 3 instructions in the worst case. This is because the URM can compare the contents of two registers in a single step.

Turing Machine Program:

A Turing Machine, on the other hand, would need to compare the binary representations of $x$ and $y$ bit by bit. This process involves scanning the tape, comparing corresponding bits, and potentially moving back and forth on the tape. The time complexity of this process is $\Theta(n^2)$, where $n$ is the number of bits in the binary representation of the input numbers. This is because, in the worst case, the Turing machine might need to compare all bits of both numbers, and for each bit comparison, it might need to traverse the tape. The Turing Machine’s bit-by-bit comparison is a much more fundamental operation than the URM’s direct comparison of register contents, which highlights the differences in the power of these models.

Input: Binary representations of $x$ and $y$ on the tape, separated by a blank symbol. Move the head to the beginning of the tape. while not at the end of either number do Read the current bits of $x$ and $y$. if the bits are different then Output 0 (No) and halt. end if Move the head to the next bits of $x$ and $y$. end while if both numbers are finished then Output 1 (Yes) and halt. else Output 0 (No) and halt. end if

Algorithm [alg:tm_equality] shows a high-level description of a Turing Machine algorithm for checking the equality of two numbers. The algorithm scans the tape, compares the bits, and outputs the result. The complexity of this algorithm is $\Theta(n^2)$ where $n$ is the number of bits of the input.

Extended Church-Turing Thesis

The Church-Turing thesis and its extended version are fundamental concepts in the theory of computation. They provide a framework for understanding the limits of what can be computed and how different computational models relate to each other in terms of both computability and efficiency.

Church-Turing Thesis

Informal Statement: Any function that is intuitively computable can be computed by a Turing Machine.

The Church-Turing thesis is a statement about the nature of computation. It asserts that any function that can be intuitively computed by any mechanical means can also be computed by a Turing Machine. This means that if an algorithm can be described in a way that a human can understand and execute step-by-step, then a Turing Machine can also perform that computation. In other words, the Turing Machine is a universal model of computation, capable of simulating any other computational process. This thesis is a cornerstone of computer science, suggesting that the Turing Machine captures the essence of what it means to compute.

This thesis is not a mathematical theorem that can be proven, but rather a statement that is widely accepted based on extensive evidence and the lack of any counterexamples. It is a philosophical statement about the limits of computation and provides a strong foundation for the study of computability and complexity. The thesis implies that if a problem cannot be solved by a Turing Machine, it cannot be solved by any other computational model.

Extended Church-Turing Thesis

Informal Statement: Any reasonable model of computation is polynomially related to Turing Machines.

The Extended Church-Turing thesis is a stronger statement that relates the efficiency of computation across different models. It asserts that any reasonable model of computation is polynomially related to Turing Machines. This means that if a problem can be solved in time $O(f(n))$ on a Turing Machine, it can be solved in time $P(f(n))$ on any other reasonable model, where $P$ is a polynomial function. Conversely, if a problem can be solved in time $O(g(n))$ on a reasonable model, it can be solved in time $Q(g(n))$ on a Turing Machine, where $Q$ is also a polynomial. This implies that the time complexity of a problem is roughly the same, up to a polynomial factor, across different reasonable models of computation.

This thesis implies that the notion of polynomial-time computability is robust across different computational models. If a problem is solvable in polynomial time on one reasonable model, it is also solvable in polynomial time on any other reasonable model, and in particular on a Turing Machine. This robustness is a key reason why the class of polynomial-time solvable problems (P) is considered a fundamental class in complexity theory.

Reasonable Model: The key term here is "reasonable." A computational model is considered reasonable if its basic operations have a time complexity that depends on the number of bits involved in the operation. This is known as the logarithmic cost criterion. For example, operations like addition and multiplication should have a cost that is proportional to the number of bits in the operands, rather than being treated as constant-time operations. This is crucial to avoid models that can perform computations in polynomial time that would require exponential time on a Turing Machine. The logarithmic cost criterion ensures that the cost of operations reflects the actual computational effort required, especially when dealing with large numbers. Without this criterion, it would be possible to construct models that appear to solve problems efficiently but are not realistic in terms of actual computation.

Illustration of the Extended Church-Turing Thesis. Reasonable models of computation are polynomially related to Turing Machines.

Figure 3 illustrates the concept of polynomial equivalence between different reasonable models of computation and Turing Machines.

Logarithmic Cost Criterion vs. Uniform Cost Criterion

When analyzing the complexity of algorithms, it is crucial to define how the cost of basic operations is measured. Two common approaches are the uniform cost criterion and the logarithmic cost criterion. The choice between these criteria can significantly impact the resulting complexity analysis, especially when dealing with operations that manipulate large numbers. The uniform cost criterion is often used for simplicity, but it can lead to inaccurate results in certain scenarios, while the logarithmic cost criterion provides a more realistic measure of computational effort.

Uniform Cost Criterion: Under this criterion, each basic operation is assumed to have a constant cost, regardless of the size of the operands involved. For example, adding two numbers or multiplying two numbers is considered to take a single unit of time, irrespective of the number of bits in the numbers. This criterion is often used in introductory algorithm analysis due to its simplicity.
Logarithmic Cost Criterion: Under this criterion, the cost of an operation depends on the number of bits involved in the operation. For example, adding two $n$-bit numbers would have a cost proportional to $n$, and multiplying two $n$-bit numbers would have a cost proportional to $n^2$ (using the standard multiplication algorithm). This criterion provides a more accurate representation of the actual computational effort required for operations on large numbers.

The uniform cost criterion is often used in introductory algorithm analysis because it simplifies the analysis and is suitable for algorithms where the size of the numbers being manipulated does not grow significantly with the input size. However, it can lead to misleading results when dealing with operations that can produce very large numbers, as we will see in the following example. The logarithmic cost criterion is more appropriate when the size of the numbers being manipulated can grow substantially during the computation.

Example: URM with Product

To illustrate the difference between the two cost criteria, let’s consider a modified URM that includes an additional instruction $P_i$, which computes the square of the content of register $R_i$ (i.e., $R_i \leftarrow R_i \times R_i$). This example will show how the choice of cost criterion can drastically affect the perceived complexity of an algorithm.

Program: Consider the following URM program, where the input $x$ is initially in register $R_0$, and all other registers are initialized to 0:

$T_{0,1}$ (Copy the content of $R_0$ to $R_1$, so $R_1 \leftarrow x$)
$J_{1,2,6}$ (If $R_1 = R_2$, jump to instruction 6)
$P_0$ (Compute $R_0 \leftarrow R_0 \times R_0$)
$S_2$ (Increment $R_2$ by 1)
$J_{0,0,2}$ (Jump to instruction

This program computes the value $x^{2^x}$ in register $R_0$. Let’s analyze its complexity under both cost criteria.

Analysis under Uniform Cost Criterion: Under the uniform cost criterion, each instruction is assumed to take constant time. The loop from instruction 2 to 5 is executed $x$ times. Therefore, the total time complexity of this program is $O(x)$. This analysis suggests that the program runs in linear time with respect to the input $x$.

Analysis under Logarithmic Cost Criterion: Under the logarithmic cost criterion, the cost of the product operation $P_0$ depends on the number of bits in the register $R_0$. The value in $R_0$ grows exponentially with each iteration of the loop. After $k$ iterations, the value in $R_0$ is $x^{2^k}$. The number of bits in this value is approximately $\log(x^{2^k}) = 2^k \log(x)$. Therefore, the cost of the product operation in the $k$-th iteration is proportional to $(2^k \log(x))^2$, assuming a standard multiplication algorithm. The total cost of the program is the sum of the costs of all iterations, which is at least exponential in $x$. This analysis reveals that the program’s actual complexity is much higher than what the uniform cost criterion suggests.

Turing Machine Complexity: A Turing Machine would require at least exponential time to compute $x^{2^x}$. The number of bits in the result is exponential in $x$, and since a Turing Machine can modify at most one bit per step, it would require at least an exponential number of steps to write the result on the tape. This is consistent with the logarithmic cost criterion analysis.

Explanation: The example demonstrates that the uniform cost criterion can be misleading when dealing with operations that significantly increase the size of the numbers being manipulated. The product operation in the URM is too powerful when considered as a constant-time operation. Under the logarithmic cost criterion, the cost of multiplication should be proportional to the square of the number of bits involved, which aligns with the actual cost of performing multiplication at a low level. This example highlights the importance of using the logarithmic cost criterion when analyzing the complexity of algorithms that involve operations on large numbers. The logarithmic cost criterion provides a more accurate representation of the computational effort required, especially when the size of the numbers being manipulated grows significantly during the computation.

Comparison of Uniform and Logarithmic Cost Criteria. The logarithmic cost criterion provides a more accurate analysis when dealing with operations that manipulate large numbers.

Figure 4 illustrates the difference between the uniform and logarithmic cost criteria. The uniform cost criterion simplifies the analysis but can be misleading, while the logarithmic cost criterion provides a more accurate representation of the computational effort.

Conclusion

In this document, we have explored the foundational concepts of classical complexity theory, emphasizing the importance of choosing appropriate computational models and cost criteria for accurate complexity analysis. We have seen how different models and cost criteria can lead to different conclusions about the efficiency of algorithms. The key takeaways are:

The choice of computational model and cost criterion is crucial for obtaining meaningful results in complexity analysis. Different models, such as Turing Machines and Unlimited Register Machines (URMs), can lead to different complexity results for the same problem. The Turing Machine, while being a low-level model, is a standard for theoretical analysis.
The logarithmic cost criterion is necessary when dealing with operations that significantly increase the size of intermediate results during computation. This criterion ensures that the cost of operations is proportional to the number of bits involved, reflecting the actual cost of performing these operations at a low level. The uniform cost criterion, while simpler, can be misleading in such scenarios.
The Church-Turing thesis states that any function that can be intuitively computed can be computed by a Turing Machine. This thesis establishes the Turing Machine as a universal model of computation.
The extended Church-Turing thesis asserts that any reasonable model of computation is polynomially related to Turing Machines. This implies that the notion of polynomial-time computability is robust across different computational models. It provides a strong justification for focusing on polynomial-time solvability as a measure of efficiency.
The class P (polynomial time), which includes all languages that can be decided by a Turing Machine in polynomial time, is invariant with respect to the model of computation under the extended Church-Turing thesis. This means that if a problem can be solved in polynomial time on a Turing Machine, it can also be solved in polynomial time on any other reasonable model of computation. This invariance is a crucial property of the class P.

Note: The extended Church-Turing thesis implies that if a problem cannot be solved in polynomial time on a Turing Machine, it cannot be solved in polynomial time on any other reasonable model of computation. This is a crucial concept for understanding the limits of efficient computation. The extendedChurch-Turing thesis provides a strong argument for the importance of the class P, as it suggests that problems outside of P are inherently difficult to solve efficiently.

Further Reading:

For a deeper understanding of the topics covered in this document, we recommend the following resources:

"Computational Complexity" by Christos H. Papadimitriou: This book provides a comprehensive introduction to the field of computational complexity theory and is the main reference for this part of the course.
Information about the Church-Turing thesis: Numerous online resources and articles provide detailed explanations of the Church-Turing thesis and its implications. These resources can help in understanding the philosophical and theoretical underpinnings of the thesis.

This document serves as an introduction to the fundamental concepts of classical complexity theory. Further exploration of these topics will be necessary to fully grasp the intricacies of computational complexity. The concepts discussed here will serve as the basis for future discussions on specific complexity classes and the relationships between them.

--- title: "Introduction to Classical Complexity Theory" 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 introduces the fundamental concepts of classical complexity theory. We will primarily focus on *decision problems* and their classification, exploring the distinctions between decisional, functional, and optimization problems. Understanding these problem types is crucial for framing computational challenges within a rigorous theoretical context. We will then introduce *computational models*, specifically Turing Machines and Unlimited Register Machines (URMs), which serve as abstract machines for analyzing the complexity of algorithms. These models allow us to quantify the resources required to solve computational problems. Furthermore, we will discuss the *Church-Turing thesis* and its extended version, emphasizing the significance of the *logarithmic cost criterion* in accurate complexity analysis. This criterion is essential when dealing with operations that significantly increase the size of intermediate results during computation, as it provides a more realistic measure of computational effort. The document aims to provide a solid foundation for understanding the theoretical underpinnings of computational complexity, setting the stage for more advanced topics in the field. The content of this document is based on the book \"Computational Complexity\" by Christos H. Papadimitriou, which serves as the main reference for this part of the course. ::: tcolorbox - **Decision Problems**: Problems with a yes/no answer. - **Computational Models**: Abstract machines (e.g., Turing Machines, URMs) for analyzing algorithm complexity. - **Church-Turing Thesis**: The assertion that any function computable by an algorithm can be computed by a Turing Machine. - **Extended Church-Turing Thesis**: The assertion that any reasonable model of computation is polynomially related to Turing Machines. - **Logarithmic Cost Criterion**: A method for measuring the cost of operations based on the number of bits involved. ::: # Types of Computational Problems Computational problems can be broadly classified into three distinct categories, each with different requirements for their solutions. These categories help in understanding the nature of the problem and the type of algorithms that might be suitable for solving them: - **Decisional Problems**: These problems require a binary decision, with the output being either \"yes\" or \"no\". They are concerned with determining whether a given input satisfies a specific property. The focus is on the existence of a solution rather than the solution itself. For example, determining if a given graph is Hamiltonian is a decisional problem. - **Functional Problems**: These problems require the computation of a specific output based on the given input. The output is not limited to a binary choice but can be any value or structure. The goal is to construct a solution. For example, finding a Hamiltonian path in a graph, if one exists, is a functional problem. - **Optimization Problems**: These problems involve finding the best solution among a set of feasible solutions, according to a given cost function. The goal is to minimize or maximize the cost function. The focus is on finding the optimal solution among many possibilities. For example, finding the Hamiltonian path with the minimum cost, where a cost is associated with each path, is an optimization problem. ## Example: Hamiltonian Path Problem To illustrate these categories, we will use the *Hamiltonian Path Problem* as a running example. This problem is well-known in graph theory and serves as a good example to differentiate the three types of problems. ::: tcolorbox []{#def:hamiltonian_path label="def:hamiltonian_path"} A Hamiltonian path in a graph is a path that visits each vertex exactly once. ::: The Hamiltonian Path Problem can be formulated in each of the three categories as follows: - **Decisional**: Given a graph $G$, determine whether a Hamiltonian path exists in $G$. The output is a binary decision: \"yes\" if a Hamiltonian path exists, and \"no\" otherwise. - **Functional**: Given a graph $G$, find and output a Hamiltonian path if it exists. If no Hamiltonian path exists, the output should indicate \"does not exist\". The output is a specific path or a notification of its absence. - **Optimization**: Given a graph $G$ and a cost function defined on paths, find the Hamiltonian path with the minimum cost. This requires evaluating the cost of all possible Hamiltonian paths and selecting the one with the lowest cost. The output is the optimal path according to the cost function. <figure id="fig:hamiltonian_graphs"> <figcaption>Examples of graphs with and without Hamiltonian paths. The red path indicates a Hamiltonian path in the left graph.</figcaption> </figure> Figure [1](#fig:hamiltonian_graphs){reference-type="ref" reference="fig:hamiltonian_graphs"} shows two example graphs. The graph on the left has a Hamiltonian path $A \to B \to C \to D$, while the graph on the right does not have a Hamiltonian path. # Decision Problems and Languages In this course, we will primarily focus on *decision problems*. A decision problem can be conceptualized as a process that partitions the set of all possible inputs into two distinct subsets: those for which the answer is \"yes\" and those for which the answer is \"no\". This binary classification allows us to represent decision problems using the concept of formal languages, which provides a powerful framework for studying their complexity. ::: tcolorbox []{#def:language label="def:language"} A language $L$ over an alphabet $\Sigma$ is a set of strings formed by concatenating symbols from $\Sigma$. Formally, $L \subseteq \Sigma^*$, where $\Sigma^*$ denotes the set of all possible strings over $\Sigma$. The alphabet $\Sigma$ is a finite set of symbols. ::: For any given decision problem, we can define a corresponding language $L$ as the set of all inputs for which the answer to the problem is \"yes\". This language $L$ is a subset of $\Sigma^*$, where $\Sigma$ is the alphabet used to encode the inputs. The \"no\" instances are implicitly represented by the complement of $L$ with respect to $\Sigma^*$, denoted as $\Sigma^* \setminus L$. Thus, studying decision problems is equivalent to studying languages. ## Example: Hamiltonian Path Language Let's consider the Hamiltonian Path Problem again. We can define a language $L_{HP}$ that represents this problem as follows: $$L_{HP} = \{G \mid G \text{ is a graph with a Hamiltonian path}\}$$ Here, $L_{HP}$ is the set of all graph encodings that represent graphs containing a Hamiltonian path. The elements of $L_{HP}$ are strings over some alphabet $\Sigma$ that, when decoded, represent graphs with a Hamiltonian path. ## Encoding Graphs To work with graphs as inputs to algorithms, we need to encode them as strings over a given alphabet. A common approach is to use binary strings, which allows for a uniform representation of various data structures. For example, a graph $G = (V, E)$ can be encoded as follows: - Let $|V| = n$ be the number of vertices in the graph. - The vertices are named $1, 2, \dots, n$. - The edges are represented as pairs $(i, j)$, where $i, j \in \{1, 2, \dots, n\}$. - A possible encoding is: $\text{bin}(n) \# \text{bin}(i_1) \# \text{bin}(j_1) \# \# \text{bin}(i_2) \# \text{bin}(j_2) \# \# \dots$, where $\text{bin}(x)$ represents the binary encoding of the integer $x$, and $(i_k, j_k)$ are the edges of the graph. The symbol $\#$ is used as a separator to distinguish between different parts of the encoding. <figure id="fig:graph_encoding"> <figcaption>Example of a graph and its encoding.</figcaption> </figure> Figure [2](#fig:graph_encoding){reference-type="ref" reference="fig:graph_encoding"} shows an example of a graph and its corresponding encoding. The graph has 3 nodes and 3 edges. The encoding represents the number of nodes, followed by the edges. **Note:** It is important to note that not all strings over the chosen alphabet will represent valid encodings of graphs. For instance, a string might not conform to the specified format or might represent a graph with invalid edge specifications. These strings that do not represent valid graph encodings are typically considered as \"no\" instances of the decision problem and are therefore not part of the language $L_{HP}$. It is generally assumed that checking whether a string is a valid encoding can be done efficiently (e.g., in linear time and constant space). This assumption is crucial for the subsequent analysis of computational complexity. # Computational Models To analyze the complexity of computational problems, we need to define abstract *computational models*. These models provide a formal framework for describing algorithms and measuring their resource usage, such as time and space. In this course, we will primarily use *Turing Machines* as our standard model due to their simplicity and theoretical significance. However, we will also briefly discuss *Unlimited Register Machines (URMs)* to highlight potential issues and subtleties in complexity analysis when using different models, particularly concerning the cost of basic operations. ## Turing Machines A *Turing Machine* (TM) is a theoretical model of computation that consists of a finite-state control unit, an infinite tape divided into cells, and a read/write head that can move along the tape. The Turing Machine is a very low-level model, which makes it suitable for studying the fundamental limits of computation. Formally, a Turing Machine $M$ can be defined as a tuple $(Q, \Sigma, \delta, q_0)$, where: - $Q$ is a finite set of states, representing the internal configurations of the machine. - $\Sigma$ is a finite set of tape symbols (the alphabet), including a special blank symbol. - $\delta: Q \times \Sigma \rightarrow Q \times \Sigma \times \{L, R, S\}$ is the transition function, which dictates the machine's behavior based on its current state and the symbol it reads. $\delta(q, a) = (q', a', d)$ means that if the machine is in state $q$ and reads symbol $a$, it transitions to state $q'$, writes symbol $a'$ on the tape, and moves the head according to $d$, where $L$ means move left, $R$ means move right, and $S$ means stay in the same position. - $q_0 \in Q$ is the initial state, where the machine starts its computation. The machine operates by reading the symbol in the current cell, applying the transition function to determine the next state, writing a new symbol in the cell, and moving the head left, right, or staying in the same position. The computation continues until the machine reaches a halting state, which is a state where no transition is defined for the current symbol. ## Unlimited Register Machines (URMs) An *Unlimited Register Machine* (URM) is another model of computation that uses an infinite set of registers, $R_0, R_1, R_2, \dots$, each capable of storing an arbitrarily large non-negative integer. The URM operates by executing a sequence of instructions that manipulate the contents of these registers. Unlike Turing Machines, URMs operate on integers directly, which can sometimes lead to more concise programs for certain problems. The basic instructions of a URM are: - $S_i$: Increment the content of register $R_i$ by 1 (i.e., $R_i \leftarrow R_i + 1$). - $Z_i$: Set the content of register $R_i$ to 0 (i.e., $R_i \leftarrow 0$). - $T_{i,j}$: Transfer the content of register $R_i$ to register $R_j$ (i.e., $R_j \leftarrow R_i$). - $J_{i,j,u}$: Jump to instruction $u$ if the content of register $R_i$ is equal to the content of register $R_j$. Otherwise, proceed to the next instruction in sequence. This instruction allows for conditional execution and looping. A URM program is a finite sequence of these instructions. The input to the program is typically placed in register $R_0$ (and possibly other registers), and the output is found in register $R_0$ upon termination. The program terminates when it attempts to jump to a non-existent instruction. ### Example: Deciding Equality of Two Numbers To illustrate the differences in complexity analysis between Turing Machines and URMs, let's consider the problem of deciding whether two given numbers are equal. This example demonstrates how different computational models can lead to different complexity results for the same problem. **Problem**: Given two non-negative integers, $x$ in register $R_0$ and $y$ in register $R_1$, decide if $x = y$. The output should be 1 in $R_0$ if $x=y$ and 0 otherwise. **URM Program:** The following URM program solves the equality problem: 1. []{#urm_eq_1 label="urm_eq_1"} $J_{0,1,4}$ (If $R_0 = R_1$, jump to instruction 4) 2. []{#urm_eq_2 label="urm_eq_2"} $Z_0$ (Set $R_0$ to 0) 3. []{#urm_eq_3 label="urm_eq_3"} $J_{0,0,100}$ (Jump to instruction 100, which terminates the program) 4. []{#urm_eq_4 label="urm_eq_4"} $Z_0$ (Set $R_0$ to 0) 5. []{#urm_eq_5 label="urm_eq_5"} $S_0$ (Increment $R_0$ by 1) 6. []{#urm_eq_6 label="urm_eq_6"} $J_{0,0,100}$ (Jump to instruction 100, which terminates the program) This URM program has a constant time complexity, as it executes a fixed number of instructions (at most 6) regardless of the input values. Specifically, it executes at most 3 instructions in the worst case. This is because the URM can compare the contents of two registers in a single step. **Turing Machine Program:** A Turing Machine, on the other hand, would need to compare the binary representations of $x$ and $y$ bit by bit. This process involves scanning the tape, comparing corresponding bits, and potentially moving back and forth on the tape. The time complexity of this process is $\Theta(n^2)$, where $n$ is the number of bits in the binary representation of the input numbers. This is because, in the worst case, the Turing machine might need to compare all bits of both numbers, and for each bit comparison, it might need to traverse the tape. The Turing Machine's bit-by-bit comparison is a much more fundamental operation than the URM's direct comparison of register contents, which highlights the differences in the power of these models. :::: algorithm ::: algorithmic **Input:** Binary representations of $x$ and $y$ on the tape, separated by a blank symbol. Move the head to the beginning of the tape. **while** not at the end of either number **do** Read the current bits of $x$ and $y$. **if** the bits are different **then** Output 0 (No) and halt. **end if** Move the head to the next bits of $x$ and $y$. **end while** **if** both numbers are finished **then** Output 1 (Yes) and halt. **else** Output 0 (No) and halt. **end if** ::: :::: Algorithm [\[alg:tm_equality\]](#alg:tm_equality){reference-type="ref" reference="alg:tm_equality"} shows a high-level description of a Turing Machine algorithm for checking the equality of two numbers. The algorithm scans the tape, compares the bits, and outputs the result. The complexity of this algorithm is $\Theta(n^2)$ where $n$ is the number of bits of the input. # Extended Church-Turing Thesis The *Church-Turing thesis* and its extended version are fundamental concepts in the theory of computation. They provide a framework for understanding the limits of what can be computed and how different computational models relate to each other in terms of both computability and efficiency. ## Church-Turing Thesis ::: tcolorbox []{#thm:church_turing label="thm:church_turing"} **Informal Statement:** Any function that is intuitively computable can be computed by a Turing Machine. ::: The *Church-Turing thesis* is a statement about the nature of computation. It asserts that any function that can be intuitively computed by any mechanical means can also be computed by a Turing Machine. This means that if an algorithm can be described in a way that a human can understand and execute step-by-step, then a Turing Machine can also perform that computation. In other words, the Turing Machine is a universal model of computation, capable of simulating any other computational process. This thesis is a cornerstone of computer science, suggesting that the Turing Machine captures the essence of what it means to compute. This thesis is not a mathematical theorem that can be proven, but rather a statement that is widely accepted based on extensive evidence and the lack of any counterexamples. It is a philosophical statement about the limits of computation and provides a strong foundation for the study of computability and complexity. The thesis implies that if a problem cannot be solved by a Turing Machine, it cannot be solved by any other computational model. ## Extended Church-Turing Thesis ::: tcolorbox []{#thm:extended_church_turing label="thm:extended_church_turing"} **Informal Statement:** Any reasonable model of computation is polynomially related to Turing Machines. ::: The *Extended Church-Turing thesis* is a stronger statement that relates the efficiency of computation across different models. It asserts that any *reasonable* model of computation is polynomially related to Turing Machines. This means that if a problem can be solved in time $O(f(n))$ on a Turing Machine, it can be solved in time $P(f(n))$ on any other reasonable model, where $P$ is a polynomial function. Conversely, if a problem can be solved in time $O(g(n))$ on a reasonable model, it can be solved in time $Q(g(n))$ on a Turing Machine, where $Q$ is also a polynomial. This implies that the time complexity of a problem is roughly the same, up to a polynomial factor, across different reasonable models of computation. This thesis implies that the notion of polynomial-time computability is robust across different computational models. If a problem is solvable in polynomial time on one reasonable model, it is also solvable in polynomial time on any other reasonable model, and in particular on a Turing Machine. This robustness is a key reason why the class of polynomial-time solvable problems (P) is considered a fundamental class in complexity theory. **Reasonable Model**: The key term here is \"reasonable.\" A computational model is considered reasonable if its basic operations have a time complexity that depends on the number of bits involved in the operation. This is known as the *logarithmic cost criterion*. For example, operations like addition and multiplication should have a cost that is proportional to the number of bits in the operands, rather than being treated as constant-time operations. This is crucial to avoid models that can perform computations in polynomial time that would require exponential time on a Turing Machine. The logarithmic cost criterion ensures that the cost of operations reflects the actual computational effort required, especially when dealing with large numbers. Without this criterion, it would be possible to construct models that appear to solve problems efficiently but are not realistic in terms of actual computation. <figure id="fig:extended_church_turing"> <figcaption>Illustration of the Extended Church-Turing Thesis. Reasonable models of computation are polynomially related to Turing Machines.</figcaption> </figure> Figure [3](#fig:extended_church_turing){reference-type="ref" reference="fig:extended_church_turing"} illustrates the concept of polynomial equivalence between different reasonable models of computation and Turing Machines. # Logarithmic Cost Criterion vs. Uniform Cost Criterion When analyzing the complexity of algorithms, it is crucial to define how the cost of basic operations is measured. Two common approaches are the *uniform cost criterion* and the *logarithmic cost criterion*. The choice between these criteria can significantly impact the resulting complexity analysis, especially when dealing with operations that manipulate large numbers. The uniform cost criterion is often used for simplicity, but it can lead to inaccurate results in certain scenarios, while the logarithmic cost criterion provides a more realistic measure of computational effort. - **Uniform Cost Criterion**: Under this criterion, each basic operation is assumed to have a constant cost, regardless of the size of the operands involved. For example, adding two numbers or multiplying two numbers is considered to take a single unit of time, irrespective of the number of bits in the numbers. This criterion is often used in introductory algorithm analysis due to its simplicity. - **Logarithmic Cost Criterion**: Under this criterion, the cost of an operation depends on the number of bits involved in the operation. For example, adding two $n$-bit numbers would have a cost proportional to $n$, and multiplying two $n$-bit numbers would have a cost proportional to $n^2$ (using the standard multiplication algorithm). This criterion provides a more accurate representation of the actual computational effort required for operations on large numbers. The uniform cost criterion is often used in introductory algorithm analysis because it simplifies the analysis and is suitable for algorithms where the size of the numbers being manipulated does not grow significantly with the input size. However, it can lead to misleading results when dealing with operations that can produce very large numbers, as we will see in the following example. The logarithmic cost criterion is more appropriate when the size of the numbers being manipulated can grow substantially during the computation. ## Example: URM with Product ::: tcolorbox To illustrate the difference between the two cost criteria, let's consider a modified URM that includes an additional instruction $P_i$, which computes the square of the content of register $R_i$ (i.e., $R_i \leftarrow R_i \times R_i$). This example will show how the choice of cost criterion can drastically affect the perceived complexity of an algorithm. **Program:** Consider the following URM program, where the input $x$ is initially in register $R_0$, and all other registers are initialized to 0: 1. []{#urm_prod_1 label="urm_prod_1"} $T_{0,1}$ (Copy the content of $R_0$ to $R_1$, so $R_1 \leftarrow x$) 2. []{#urm_prod_2 label="urm_prod_2"} $J_{1,2,6}$ (If $R_1 = R_2$, jump to instruction 6) 3. []{#urm_prod_3 label="urm_prod_3"} $P_0$ (Compute $R_0 \leftarrow R_0 \times R_0$) 4. []{#urm_prod_4 label="urm_prod_4"} $S_2$ (Increment $R_2$ by 1) 5. []{#urm_prod_5 label="urm_prod_5"} $J_{0,0,2}$ (Jump to instruction 2) This program computes the value $x^{2^x}$ in register $R_0$. Let's analyze its complexity under both cost criteria. **Analysis under Uniform Cost Criterion:** Under the uniform cost criterion, each instruction is assumed to take constant time. The loop from instruction 2 to 5 is executed $x$ times. Therefore, the total time complexity of this program is $O(x)$. This analysis suggests that the program runs in linear time with respect to the input $x$. **Analysis under Logarithmic Cost Criterion:** Under the logarithmic cost criterion, the cost of the product operation $P_0$ depends on the number of bits in the register $R_0$. The value in $R_0$ grows exponentially with each iteration of the loop. After $k$ iterations, the value in $R_0$ is $x^{2^k}$. The number of bits in this value is approximately $\log(x^{2^k}) = 2^k \log(x)$. Therefore, the cost of the product operation in the $k$-th iteration is proportional to $(2^k \log(x))^2$, assuming a standard multiplication algorithm. The total cost of the program is the sum of the costs of all iterations, which is at least exponential in $x$. This analysis reveals that the program's actual complexity is much higher than what the uniform cost criterion suggests. **Turing Machine Complexity:** A Turing Machine would require at least exponential time to compute $x^{2^x}$. The number of bits in the result is exponential in $x$, and since a Turing Machine can modify at most one bit per step, it would require at least an exponential number of steps to write the result on the tape. This is consistent with the logarithmic cost criterion analysis. **Explanation:** The example demonstrates that the uniform cost criterion can be misleading when dealing with operations that significantly increase the size of the numbers being manipulated. The product operation in the URM is too powerful when considered as a constant-time operation. Under the logarithmic cost criterion, the cost of multiplication should be proportional to the square of the number of bits involved, which aligns with the actual cost of performing multiplication at a low level. This example highlights the importance of using the logarithmic cost criterion when analyzing the complexity of algorithms that involve operations on large numbers. The logarithmic cost criterion provides a more accurate representation of the computational effort required, especially when the size of the numbers being manipulated grows significantly during the computation. ::: <figure id="fig:cost_criteria"> <figcaption>Comparison of Uniform and Logarithmic Cost Criteria. The logarithmic cost criterion provides a more accurate analysis when dealing with operations that manipulate large numbers.</figcaption> </figure> Figure [4](#fig:cost_criteria){reference-type="ref" reference="fig:cost_criteria"} illustrates the difference between the uniform and logarithmic cost criteria. The uniform cost criterion simplifies the analysis but can be misleading, while the logarithmic cost criterion provides a more accurate representation of the computational effort. # Conclusion In this document, we have explored the foundational concepts of classical complexity theory, emphasizing the importance of choosing appropriate computational models and cost criteria for accurate complexity analysis. We have seen how different models and cost criteria can lead to different conclusions about the efficiency of algorithms. The key takeaways are: - The choice of computational model and cost criterion is crucial for obtaining meaningful results in complexity analysis. Different models, such as Turing Machines and Unlimited Register Machines (URMs), can lead to different complexity results for the same problem. The Turing Machine, while being a low-level model, is a standard for theoretical analysis. - The *logarithmic cost criterion* is necessary when dealing with operations that significantly increase the size of intermediate results during computation. This criterion ensures that the cost of operations is proportional to the number of bits involved, reflecting the actual cost of performing these operations at a low level. The uniform cost criterion, while simpler, can be misleading in such scenarios. - The *Church-Turing thesis* states that any function that can be intuitively computed can be computed by a Turing Machine. This thesis establishes the Turing Machine as a universal model of computation. - The *extended Church-Turing thesis* asserts that any reasonable model of computation is polynomially related to Turing Machines. This implies that the notion of polynomial-time computability is robust across different computational models. It provides a strong justification for focusing on polynomial-time solvability as a measure of efficiency. - The class **P** (polynomial time), which includes all languages that can be decided by a Turing Machine in polynomial time, is invariant with respect to the model of computation under the extended Church-Turing thesis. This means that if a problem can be solved in polynomial time on a Turing Machine, it can also be solved in polynomial time on any other reasonable model of computation. This invariance is a crucial property of the class P. ::: mdframed **Note:** The extended Church-Turing thesis implies that if a problem cannot be solved in polynomial time on a Turing Machine, it cannot be solved in polynomial time on any other reasonable model of computation. This is a crucial concept for understanding the limits of efficient computation. The extendedChurch-Turing thesis provides a strong argument for the importance of the class P, as it suggests that problems outside of P are inherently difficult to solve efficiently. ::: **Further Reading:** For a deeper understanding of the topics covered in this document, we recommend the following resources: - *\"Computational Complexity\"* by Christos H. Papadimitriou: This book provides a comprehensive introduction to the field of computational complexity theory and is the main reference for this part of the course. - Information about the Church-Turing thesis: Numerous online resources and articles provide detailed explanations of the Church-Turing thesis and its implications. These resources can help in understanding the philosophical and theoretical underpinnings of the thesis. This document serves as an introduction to the fundamental concepts of classical complexity theory. Further exploration of these topics will be necessary to fully grasp the intricacies of computational complexity. The concepts discussed here will serve as the basis for future discussions on specific complexity classes and the relationships between them.