Eth, Nexp Vs Exp And The Np Vs Qp Problem

Defining ETH, NEXP, and EXP

The Exponential Time Hypothesis (ETH) is a conjecture in computational complexity theory that states that 3-SAT, the satisfiability problem for Boolean formulas in 3-conjunctive normal form where each clause has at most 3 literals, cannot be solved in subexponential time by a deterministic Turing machine. More formally, ETH claims that no algorithm can solve 3-SAT in O(2^o(n)) time where n is the number of variables. This implies that 3-SAT requires exponential worst-case time complexity.

NEXP is the class of decision problems solvable by a nondeterministic Turing machine in exponential runtime, O(2^p(n)) for some polynomial p. It contains the class EXP, which consists of the decision problems solvable by a deterministic Turing machine in exponential runtime. Problems in NEXP can have exponentially long certificates to verify a yes-instance, while certificates for EXP must be of polynomial length.

ETH Conjecture States EXPs Intractability

The ETH conjecture posits that 3-SAT cannot be solved substantially faster than the brute force method of trying all possible assignments to the variables. This suggests that no polynomial-time algorithm can solve 3-SAT. If ETH holds, it would indicate EXP-completeness is an intractable property, meaning all EXP-complete problems require exponential worst-case time. Thus ETH implies that EXP problems are not solvable in subexponential time.

Table of Contents

Many natural computational problems are EXP-complete, such as solving games like chess or Go. ETH says these games cannot be solved orders of magnitude faster than just trying all possible sequences of moves. This is why even advanced chess algorithms cannot defeat the best human players – chess likely requires exponential computation.

NEXP Contains Problems Beyond EXP

While EXP consists of decision problems solvable in exponential time, NEXP contains additional search problems where the solution may be exponentially long. For example, finding a strategy to play an optimal game of chess requires search through a game tree of exponential size. The optimal chess strategy itself could be exponentially long and so solving this search problem is likely not in EXP, but contained in NEXP.

In fact, by using clever reductions from search problems to decision versions, most natural search problems with exponential search spaces can be categorized as NEXP-complete. These include problems like finding the optimal sequence of moves in games like chess and Go, or finding optimal protein foldings – exponentially hard search problems that arise frequently across science and engineering disciplines.

Explaining the NP vs QP Problem

A major open question in theoretical computer science is resolving the relationship between the complexity classes NP and QP – whether they are equal or if one is strictly contained in the other. Informally, NP represents decision problems with efficiently verifiable solutions, while QP consists of problems solvable quickly on a quantum computer.

It is known that P, the class of problems efficiently solvable by a classical (non-quantum) computer, is contained in NP intersect QP. However, the containment relationships between NP and QP remain a mystery. NP contains many important problems like integer factoring and graph isomorphism that we do not know how to efficiently solve classically or quantumly.

Polynomial Hierarchy and Oracle Machines

The polynomial hierarchy generalizes the classes P and NP into an infinite hierarchy based on oracle machines. An oracle machine can solve a decision problem in polynomial time given the ability to call an “oracle” which instantly solves instances of some other decision problem. For example, using an NP-complete oracle gives rise to the class NP^NP.

This construction of oracle machines defines the polynomial hierarchy: P ⊆ NP ⊆ NP^NP ⊆ NP^NP^NP…. Higher levels of the hierarchy characterize the complexity of problems involving sequential calls to oracles for problems at lower levels. The relationship between the polynomial hierarchy and complexity classes like PSPACE remains unclear.

Open Problems in Complexity Theory

Understanding the relationships between core complexity classes like P, NP, EXP, NEXP, QP, and beyond is the source of many major open research problems:

Does P = NP? Are efficiently verifiable problems efficiently solvable?
Is the ETH conjecture true? Are all EXP problems inherently intractable?
Can quantum computers efficiently solve problems beyond classical computers (P vs QP)?
Where do classes like NP, PSPACE, EXP, NEXP fit within the polynomial hierarchy?

Resolving these questions could unlock both theoretical insights and new applications for computer science, optimization, cryptography and more by defining precise boundaries on efficient computation.