Abstract: We establish more efficient methods for solving interesting classes of NP-hard problems exactly, as well as methods for proving limitations on how quickly those and other problems can be solved.

- On the negative side, we prove that a number of NP-hard problems cannot be solved too efficiently by algorithms that only use a small amount of additional workspace. Building on prior work in the area, we prove that the Boolean satisfiability problem and other hard problems require $\Omega(n^{2\cos(\pi/7)-o(1)}) \geq \Omega(n^{1.801})$ time to solve by any algorithm that uses $n^{o(1)}$ space. Stronger lower bounds are proved for solving quantified Boolean formulas with a fixed number of quantifiers. Our results are essentially model-independent, in that they hold for all reasonable random-access machine models. Furthermore, we present a formal proof system that captures all prior time-space lower bounds for satisfiability (including our own), and demonstrate how the search for better lower bounds can be {\em automated}, in not only our particular setting but also other lower bounds that follow a certain high-level pattern. We describe an implementation of an automated theorem prover and provide experimental results which strongly suggest that further improvements on the above time lower bound will require new tools and ideas.

- On the positive side, we give a general methodology for solving a large class of {\sf NP}-hard problems much faster than exhaustive search. In particular, for a problem in the class where exhaustive search of all possible solutions takes $\Theta(N)$ time, our algorithm solves the problem in $O(N^{\delta})$ time, for a universal constant $\delta < 0.792$ that depends on the complexity of multiplying two matrices over a ring. We also provide theoretical evidence that a much larger class of problems admits a similar type of algorithm.

To illustrate our results, consider the {\sc Max Cut} problem, where one is given a graph $G=(V,E)$ and integer $K$, and one wishes to determine if $G$ has a subset of vertices such that the number of edges leaving the subset is at least $K$. The obvious algorithm for {\sc Max Cut} runs in $O(\poly(n)\cdot 2^n)$ time, where $n = |V|$. Despite the problem's fundamental importance, no better algorithm was known for the general case of {\sc Max Cut}, prior to our work. Our results imply that {\sc Max Cut} {\em can} be solved in $O(\sqrt{3}^n)$ time but {\em cannot} be solved in $O(n^{1.801})$ time and $n^{o(1)}$ space.

Table of Contents

1 Introduction
2 Background
3 Introduction to Time-Space Tradeoffs for NP
4 New Time-Space Tradeoffs for NP Problems
5 Automated Search For Time Lower Bounds
6 Accelerated Algorithms For a Class of NP-Hard Problems
7 On Accelerated Algorithms for Satisfiability
8 Epilogue: Future Work