A New Algorithm Design Technique for Hard Problems, Building on Methods of Complexity Theory

摘要

Our goal is to develop a general algorithm design technique for a certain type of heuristic algorithms, so that it provably applies to a large class of hard problems. A heuristic algorithm provides a correct decision for most inputs, but may fail on some. We focus on the case when failure means that the algorithm does not return any answer, rather than returning a wrong result. This type of failure is represented by a "don't know" answer. Such algorithms are called errorless heuristics. Their advantage is that whenever the algorithm returns any answer (other than "don't know"), the answer is guaranteed to be correct. A reasonable quality measure for heuristics is the failure rate over the set of n-bit instances. When no efficient exact algorithm is available for a problem, then, ideally, we would like one with vanishing failure rate. We show, however, that this is hard to achieve: unless a complexity theoretic hypothesis fails (albeit less standard than P ≠ NP), some NP-complete problems cannot have a polynomial-time errorless heuristic algorithm with any vanishing failure rate. On the other hand, as a key result, we prove that vanishing, even exponentially small, failure rate is achievable, if we use a somewhat different accounting scheme to count the failures. This is based on special sets, that we call a-spheres, which are the images of the n-bit strings under a bijective, polynomial-time computable and polynomial-time invertible encoding function α. The α-spheres form a partition of all binary strings, with similar properties as the sets of n-bit strings. Our main result is that polynomial-time errorless heuristic algorithms exist, with exponentially low failure rates on the a-spheres, for a large class of decision problems. This class includes, surprisingly, all known intuitively natural NP-complete problems. Furthermore, the proof of the main theorem actually supplies a general scheme to construct the desired encoding and the errorless heuristic.