Applying Practice To Theory: Using Computers For Complexity Lower Bounds And Inapproximability Results

The P vs. NP Problem

A central question in theoretical computer science is whether the complexity classes P and NP are equal. The class P consists of all decision problems that can be solved in polynomial time by a deterministic Turing machine. The class NP consists of all decision problems where a “yes” answer can be verified in polynomial time given the right information or “certificate”.

Many important problems like the Boolean satisfiability problem (SAT) and the traveling salesman problem (TSP) are NP-complete – this means they are in NP and are the hardest problems in NP. If any NP-complete problem can be solved in polynomial time, all problems in NP can be as well. Unfortunately, despite intense study, no polynomial-time algorithms have been found for NP-complete problems after decades of research.

Since directly solving NP-complete problems has remained elusive, much research has focused on approximation algorithms and heuristics. These algorithms can efficiently find near-optimal solutions or solutions for restricted versions of NP-hard problems. Leveraging domain-specific knowledge can also yield better heuristic results. However, fundamentally faster worst-case algorithms for NP-complete problems would likely require a breakthrough demonstrating P=NP.

Techniques for Proving Lower Bounds

With NP-complete problems resilient to attempts at polynomial-time algorithms, significant work has gone into proving unconditional lower bounds showing these problems cannot be efficiently solved. These hardness results rely on establishing reductions showing that a newly studied problem is NP-hard.

Another important technique is diagonalization – constructing problems that differ from any problem that can be solved by a particular restricted class of algorithms, thus proving hardness for that class. For example, this approach was used by Baker, Gill, and Solovay to separate P from NP in relativized worlds where oracles provide extra information.

In addition, tools from algebra and combinatorics have yielded lower bounds through counting arguments and symmetry exploitation. For example, group theory arguments demonstrate limitations in solving hard problems like graph isomorphism. Combinatorial structures like expander graphs have also played an important role in proving hardness of approximation results.

Streamlining Inapproximability

Beyond just determining problem hardness, key results have also established limits on how closely many NP-hard optimization problems can be approximated in polynomial time. These rely on gap amplification and reduction-based proof techniques.

Gap amplification starts with a problem X that cannot be well-approximated, then uses transformations like concatenation and amplification to create a new problem Y that is much harder to approximate to any reasonable factor. Combining these transformations yields strong inapproximability results.

PCP theorems establish hardness of approximation for entire classes of problems by showing probabilistically checkable proofs (PCPs) can encode hardness very efficiently. As an example application, a PCP construction yields Max-3SAT being NP-hard to approximate beyond a 7/8 factor, matching the best algorithmic result.

Automated Reasoning Systems

While directly solving intractable problems algorithmically remains difficult, automated reasoning systems like SAT and SMT solvers have seen large improvements in their ability to navigate huge proof search spaces. This allows formally verifying some complexity hardness arguments mechanically rather than manually.

For example, state-of-the-art SAT solvers can establish lower bounds for restricted circuit size by exhaustively searching for small circuits fitting a given truth table specification. Machine learning guidance also helps direct solvers more effectively through the search space by detecting patterns in proof paths.

hard_function = create_truth_table(n)  

for circuit_size in range(1, max_size):
   circuit = generate_circuit(circuit_size) 
   if verifies(circuit, hard_function):
      return circuit 
return None # No circuit found  

By leveraging SAT solver proof search in this manner, hardness results relying on the structure of proof spaces can be established in an automated fashion instead of through intricate manual arguments.

The Path Forward

Despite substantial progress on unconditional lower bounds and hardness of approximation results, many open problems remain. Resolving the P vs. NP question remains a central challenge, but incremental progress will likely need to come from understanding restricted cases. For example, hardness results for depth-bounded circuit models could yield insights applicable to general algorithms.

In terms of techniques, finding general methods applicable across problem domains instead of tools tailored to each area will be important for further progress. Developing stronger diagonalization and algebraization arguments that can match the power of existing combinatorial approaches is also an open research direction. On the practical side, continued improvements in SAT/SMT solvers and automated reasoning systems will help tackle more complex proof challenges.

Through collaborations spanning theory and systems, the quest for hardness continues to advance – whether incrementally or with unexpected breakthroughs. Each lower bound and inapproximability result lays further bricks in the wall separating easy from hard, better delineating the true capabilities and limitations of efficient computation.