Bridging The Gap Between Computability Theory And Complexity Theory
The Gap Between Computability and Complexity
Computability theory and complexity theory are two fundamental pillars of theoretical computer science. Computability theory deals with what can and cannot be computed by algorithms, regardless of resource constraints. Complexity theory analyzes the time, space, and other resource requirements for algorithms to solve computational problems. There exists a conceptual gap between these two theories that is important to bridge.
While computability theory ignores resource constraints, complexity theory incorporates these vital considerations into understanding algorithmic limitations. Bridging this gap can lead to revelations about whether problems are unsolvable due to inherent uncomputability or due to extreme resource constraints that place them beyond feasibility. There may also exist connections between degrees of uncomputability and degrees of complexity.
Key Concepts in Computability Theory
Turing Machines and Decidability
At the core of computability theory lies Turing machines, formal abstract symbol manipulation devices capable of replicating the logic of any computer algorithm. The concept of Turing machines gives a firm mathematical foundation for analyzing what can and cannot be computed.
A decision problem is called decidable or computable if there exists a Turing machine that always halts with a yes/no answer. Problems that are undecidable or uncomputable for Turing machines represent fundamental limitations on the power of computation.
Reducibility and Degrees of Unsolvability
Many problems are uncomputable, but some lend themselves to more computational tractability than others. Reducibility formalizes what it means for one problem to be at least as difficult to solve as another.
Degrees of unsolvability classify uncomputable problems based on their relative reducibility relationships. Two problems with the same degree of unsolvability are equivalent in difficulty. This classification reveals deep connections between the inherent difficulty of problems.
Example Turing Machine for a Simple Function
As an example, we can design a simple Turing machine to compute the function f(n) = 2n. The machine will:
1. Start with the input n represented in unary with n 1’s on the tape
2. Iterate through and double each 1 to make a 1
3. Halt and output the final string of 1’s representing 2n
This Turing machine always halts with the correct output. Despite its simplicity, the machine illustrates key concepts of computability theory implemented on an abstract device.
Fundamental Concepts in Complexity Theory
Time and Space Complexity
Unlike computability theory, complexity theory analyzes how algorithm efficiency scales with input size. Two key measures are time complexity measuring computation steps and space complexity measuring memory usage.
Complexities are expressed using big O notation, such as O(n) for linear time and O(1) for constant time. The time and space requirements of algorithms on large inputs are especially important.
P, NP, and NP-Completeness
The complexity classes P and NP classify problems by efficiency of their solutions. P contains problems solvable in polynomial time by a deterministic Turing machine. NP contains problems where solutions can be verified in polynomial time.
Many problems are NP but not known to be in P. The hardest NP problems are NP-complete ones reducible to all other problems in NP. Thousands of natural NP-complete problems exist, but no polynomial-time solutions are known.
Example Algorithm Analysis
We can analyze complexity by example on a simple sorting algorithm like insertion sort. This iterates through a list while inserting each element into the proper sorted order relative to those already processed.
In the average and worst case, this makes a number of comparisons quadratic relative to the number n of items to sort. So insertion sort runs in O(n^2) time complexity, considerably slower than more advanced algorithms like quicksort with O(n log n) comparisons.
Connections Between Computability and Complexity
Complexity Classes Beyond NP
While NP represents a central complexity class, even more uncomputable problems exist at higher levels of the polynomial hierarchy or with different complexity measures like parallel time. Exploring ever-growing complexity classes reveals further gradations of complexity beyond NP.
Reductions Between Complexity Classes
As with computability theory, reductions help relate problems. Hardness reductions show containment or equivalence of problems within or across complexity classes. This allows translating intuitions between complexity classes to better understand relations between them.
Open Questions at the Boundary
Major open questions reside at the boundary between computability theory and complexity theory, such as whether P equals NP. A proof that P does not equal NP would not make NP-hard problems computable, but would confirm the mathematical separation between easy and hard problems in a complexity-theoretic sense.
Other frontier questions include whether probabilistic Turing machines can efficiently solve problems intractable for deterministic computation, or whether NP-hard problems admit approximation schemes efficiently computing near-optimal solutions for them.
