Computer Science Department
School of Computer Science, Carnegie Mellon University
Algorithms and Resource Requirements
for Fundamental Problems
Keywords: Satisfiability, lower bounds, time-space tradeoffs,
automated theorem-proving, exact algorithms, maximum cut
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
Ω(n2 cos(π/7)-o(1)) ≥ Ω(n1.801)
time to solve by any algorithm that uses
no(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 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 NP-hard problems much faster than exhaustive search.
In particular, for a problem in the class where exhaustive search of all
possible solutions takes Θ(N) time, our algorithm solves the problem
in O(Nδ) time, for a universal constant δ < 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 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
MAX CUT runs in O(poly(n)· 2n) time, where n = |V |.
Despite the problem's importance, no better algorithm was known for the
general case of MAX CUT, prior to our work. Our results imply that
MAX CUT can be solved in
O(√3n) time but cannot be solved in
O(n1.801) time and no(1) space.