🖥️Computational Complexity Theory Unit 9 – Diagonalization & Hierarchy Theorems

Key Concepts and Definitions

• Computational complexity theory studies the resources required to solve problems, focusing on time and space
• Time complexity measures the number of steps an algorithm takes to solve a problem as a function of input size
• Space complexity measures the amount of memory an algorithm uses to solve a problem as a function of input size
• Turing machines are abstract computational models used to analyze the complexity of problems
  • Deterministic Turing machines have a single computation path for each input
  • Nondeterministic Turing machines can explore multiple computation paths simultaneously
• Complexity classes are sets of problems that can be solved within specific resource bounds (polynomial time, exponential time)
• Reducibility is a technique used to show that one problem is at least as hard as another by transforming instances of one problem into instances of the other
• Oracle machines are Turing machines with access to an oracle that can solve a specific problem in a single step

Diagonalization Technique

• Diagonalization is a powerful technique used to prove separation results between complexity classes
• The technique involves constructing a language or problem that differs from every language in a given enumeration
• Diagonalization exploits the fact that there are more languages than Turing machines
• The diagonalization language is constructed by flipping the output of the i-th Turing machine on its own encoding as input
• Diagonalization proofs often involve self-reference and contradiction
  • If the diagonalization language were in the enumerated class, it would contradict its own definition
• Diagonalization can be used to prove hierarchy theorems and the existence of problems outside specific complexity classes (P ≠ NP, P ≠ EXP)

Time Hierarchy Theorem

• The Time Hierarchy Theorem states that for any time-constructible functions $f(n)$ and $g(n)$, if $f(n) = o(g(n))$, then $\text{DTIME}(f(n)) \subsetneq \text{DTIME}(g(n))$
  • In other words, more time allows Turing machines to decide strictly more languages
• The theorem implies a strict hierarchy of complexity classes based on running time (P ⊊ EXPTIME ⊊ 2EXPTIME ⊊ ...)
• The proof of the Time Hierarchy Theorem uses diagonalization to construct a language that takes too long for machines in the smaller time class to decide
• The diagonalization language simulates machines in the smaller class and does the opposite on certain inputs
• The theorem holds for both deterministic and nondeterministic time complexity classes

Space Hierarchy Theorem

• The Space Hierarchy Theorem states that for any space-constructible functions $f(n)$ and $g(n)$, if $f(n) = o(g(n))$, then $\text{DSPACE}(f(n)) \subsetneq \text{DSPACE}(g(n))$
  • More space allows Turing machines to decide strictly more languages
• The theorem implies a strict hierarchy of complexity classes based on space usage (L ⊊ PSPACE ⊊ EXPSPACE ⊊ ...)
• The proof of the Space Hierarchy Theorem also uses diagonalization, constructing a language that requires more space than machines in the smaller space class can provide
• The diagonalization language simulates machines in the smaller class and does the opposite on certain inputs, while reusing space
• The theorem holds for both deterministic and nondeterministic space complexity classes

Implications and Applications

• Hierarchy theorems provide a deeper understanding of the relationships between complexity classes
• They show that increasing the available resources (time or space) allows Turing machines to decide strictly more languages
• Hierarchy theorems can be used to prove lower bounds on the complexity of specific problems
  • If a problem is hard for a class like EXPTIME, it cannot be solved in polynomial time (assuming P ≠ EXPTIME)
• The theorems also have implications for algorithm design and optimization
  • They suggest that there are limits to the efficiency gains possible by increasing running time or memory usage
• Hierarchy theorems have been generalized to other models of computation and resource bounds (alternating Turing machines, interactive proof systems)

Proof Strategies and Techniques

• Diagonalization proofs typically involve constructing a language or problem that differs from every language in a given enumeration
• The diagonalization language is often defined using self-reference and contradiction
  • It simulates the behavior of machines in the enumeration and does the opposite on certain inputs
• Proofs of hierarchy theorems require careful resource analysis to ensure that the diagonalization language is decidable within the larger class but not the smaller one
• Padding arguments are sometimes used to extend hierarchy results to classes defined by functions that are not time- or space-constructible
• Relativization is a technique that extends hierarchy theorems to oracle complexity classes
  • An oracle is a black box that can solve a specific problem in a single step
  • Relativized hierarchy theorems show that the inclusion between oracle complexity classes is strict

Limitations and Open Problems

• Hierarchy theorems have some limitations and do not resolve all questions about the relationships between complexity classes
• They do not rule out the possibility of collapses between classes separated by functions that are not time- or space-constructible
• Hierarchy theorems do not apply to certain complexity classes, such as the polynomial hierarchy or classes defined by probabilistic or quantum models
• Some open problems related to hierarchy theorems include:
  • Proving hierarchy theorems for classes defined by simultaneous resource bounds (time and space)
  • Extending hierarchy theorems to other models of computation (Boolean circuits, decision trees)
  • Resolving the relationship between certain complexity classes (P vs. NP, P vs. BPP)

Related Complexity Classes

• Many complexity classes are defined using resource bounds related to those in the hierarchy theorems
• The polynomial hierarchy (PH) is a hierarchy of classes defined by alternating quantifiers and polynomial-time computations
  • It includes classes like NP, coNP, and $\Sigma^P_k$/$\Pi^P_k$ for each level $k$
• Exponential-time classes like EXP and NEXP are defined by exponential time bounds and are known to contain NP
• Probabilistic complexity classes like BPP and PP are defined using probabilistic Turing machines and are related to the polynomial hierarchy
• Interactive proof systems and classes like IP and MIP use interaction between provers and verifiers and are connected to the polynomial hierarchy
• Quantum complexity classes like BQP and QMA are defined using quantum models of computation and have relationships to classical complexity classes