10/27/97 - Jack Lutz
Iowa State University, visiting Cornell University
Weak Completeness and Strong Hypotheses

Despite extensive research over the past 25 years, the theory of computing has utterly failed to provide reasonable estimates of the amount of time required to solve important computational problems. The most famous instances of this failure are the NP-complete problems. A tremendous amount of experimental and theoretical evidence indicates that these problems require exponential time, but there is still no proof that they require more than linear time!

This talk surveys recent research on weak completeness--a new approach to establishing exponential lower bounds on the time required to solve computational problems. Weak completeness--a condition defined using efficiently computed betting strategies--has the following two important properties.

• Weakly complete problems are provably intractable in a very strong sense (exponential lower time bounds on exponentially many instances).

• Almost every problem solvable in exponential time is weakly complete, but is not complete, and is thus not provably intractable by standard methods. Taken together, these facts imply that weak completeness greatly extends the collection of problems that we can prove are intractable. Of course, the next step is to find "natural" examples of this phenomenon, an open problem that will be discussed.

It is possible that the NP-complete problems are themselves weakly complete. The hypothesis that this is so (roughly that NP contains a "non-negligible subset" of exponential time, a condition that implies that NP is not P) has been shown in recent years to give plausible resolutions to many questions that are not known to be resolved by "traditional" complexity-theoretic hypotheses such as the separation of the polynomial-time hierarchy. The talk will survey the explanatory power of this hypothesis and discuss recent arguments for and against its plausibility.