Lost In The In-Between: Problems Too Hard For Decidability, Too Simple For Undecidability

The In-Betweeners: Challenges in Computational Complexity

Computational complexity theory studies the inherent difficulty of computational problems. Some problems have been definitively classified as decidable or undecidable based on whether an algorithm exists that can produce a correct yes-or-no answer in finite time. However, many natural and important problems fall into an in-between zone – they are decidable in principle but intractable in practice due to astronomical resource requirements. This article explores key issues around problems that are neither practically decidable nor truly undecidable, including central open questions, examples of intermediate complexity classes, coping strategies for hardness, and philosophical perspectives.

The P versus NP Problem

The most famous question in theoretical computer science concerns the relationship between the complexity classes P and NP. The class P consists of decision problems that can be solved in polynomial time by a deterministic Turing machine. The class NP consists of problems with the property that if the answer is yes, this can be verified in polynomial time given the right certificate. NP contains all problems in P, but it also includes many problems for which no polynomial-time algorithms are known, such as the Boolean satisfiability problem of determining whether a Boolean formula can be made true by some assignment of its variables.

The P versus NP question asks whether all problems in NP are also in P – that is, can any NP problem actually be solved in polynomial time? Few believe this to be true, but no proof exists one way or the other. Resolving this question could have profound implications for many areas of science and technology. Many important practical problems like planning, scheduling, protein design and machine learning may hinge on whether P=NP. Thus, the P versus NP dilemma epitomizes the class of in-between problems that resist definitive classification as decidable or undecidable.

NP-Complete Problems

Within NP, NP-complete problems have special significance. NP-complete problems have two key properties: first, they are in NP and second, if any NP-complete problem is in P, then all problems in NP must also be in P. Thousands of natural computational problems arising in areas like routing, scheduling, logic and graph theory have been shown to be NP-complete. Well-known examples include the traveling salesman problem, graph coloring and the satisfiability problem. The ubiquity of NP-completeness means that resolving P versus NP could unlock polynomial-time algorithms across many domains.

Beyond NP-Completeness

The complexity hierarchy extends far beyond NP, with an infinite tower of complexity classes living between NP and the halting problem. This hierarchy arises from considering different machine models, resource bounds and logic-based representations. While the higher rungs of the hierarchy encode undecidable problems, many intermediate levels represent decidable but intractable complexity.

The Polynomial Hierarchy

Above NP sits the polynomial hierarchy (PH), which separates problems based on their quantifier structure. The first level contains NP and coNP, which differs in allowing a polynomial no-certificate. Higher levels have additional alternating quantifiers, allowing yes-certificates, no-certificates and so on. Unlike with NP, showing that any single level of the PH collapses would imply that the entire PH collapses into P. The PH represents a infinite ladder of potentially harder and harder complexity classes, still within the realm of decidability.

High Complexity Problems

Natural problems are known to reach high into the polynomial hierarchy and beyond. For example, graph isomorphism and integer factorization live in intermediate PH levels. In expressive logic formalisms like second order logic, the validity problem sits at high PH levels or beyond. These problems have resisted both positive and negative resolutions after decades of study by computer scientists and mathematicians.

Between Decidability and Undecidability

As well as hierarchy-based complexity, theoretical computer science quantifies complexity based on asymptotic computational resource usage. Some problems admit algorithms with high complexity while still being semantically decidable. For example, while the general Boolean circuit value problem is decidable, the fastest known algorithms require exponential time. This places the problem strictly between polynomial time decidability and true undecidability.

Many problems in PSPACE, NEXPTIME or EXPSPACE have been decisively classified as decidable yet require astronomical computational power. The exponential abyss between the easiest and hardest decidable problems helps illustrate why P versus NP is considered such a significant milestone rather than an incremental advance. Resolving P versus NP in either direction would collapse many intermediate complexity classes down to feasible computation.

Coping With Hardness

For important but potentially intractable problems like boolean satisfiability, computer scientists have devised a toolbox of coping strategies. While worst-case instances may be exponentially hard, real-world distributions often have hidden structure that algorithms can exploit.

Approximation Algorithms

Approximation algorithms find near-optimal solutions in polynomial-time at the expense of optimality guarantees. Many NP-hard problems in areas like optimization, scheduling and constraints admit simple approximation algorithms. For example, the vertex cover problem has a classic 2-approximation algorithm with provable optimality bounds.

Heuristics and Metaheuristics

Heuristics leverage problem-specific insights and properties to find good solutions quickly, without guarantees. Modern metaheuristic methods like evolutionary algorithms, tabu search and simulated annealing strategically guide underlying heuristics to balance exploration and exploitation. While lacking theoretical guarantees, heuristic methods perform well on many practical NP-hard problems.

Machine Learning

Recent breakthroughs in AI offer new hope for coping with hardness, even on problems lacking polynomial benchmarks. Machine learning, especially deep reinforcement learning, has shown promise on traditionally challenging problems like scheduling, protein folding and circuit design. The ability for neural algorithms to learn powerful representational biases from experience may provide general tools for tackling hardness.

Outlook

The boundary between decidable and undecidable continues to be a fertile area for foundational research across computer science, mathematics and logic. Both technical advances and conceptual reformulations of central open problems could await discovery by future generations.

Open Problems

Many concrete open problems still frustrate easy classification complexity-wise, acting as gatekeepers to major complexity collapses. Resolving the status of problems like graph isomorphism, integer factorization, constraint satisfaction, Nash equilibria and quantum separability would each imply a sweeping reclassification of computational power requirements across many problem domains.

New Models of Computation

New computational models like quantum computing, neuromorphic hardware and even hypothetical hypercomputers imply different formulations of the frontier between decidability and undecidability. While P vs NP and the PH hold classical secrets, new paradigms may require rethinking what is even meant by efficient computation and truth verification at their most fundamental levels.

The Lasting Mysteries

Independent of further technical breakthroughs, conceptual gaps around the source of computational complexity seem likely to persist. We can hope that in another century computer scientists may have cracked current barriers around efficeint decidability for key problems across optimization, logic, constraints, scheduling and more. However, the question “why are some problems hard?” seems to point to something inexhaustible about the mathematical structures possible in physical law itself.