The topology of provability in complexity theory

摘要

We present a general technique for showing that many properties of recursive languages are not provable. Here “provable” is taken with respect to a given sound, recursively axiomatized formal system J, such as Peano arithmetic. A representative application (Theorems 6.1–6.2) concerns the property of intractability, i.e., non-membership in the class P. It says that there exists a language E such that E is not in P, but the formal assertion ‘E is not in P’ is independent of J. Moreover, given any recursive language A ∉ P, we can construct E such that also E ⩽mP A. Our techniques strengthen similar results in the literature and lead to several other applications pertaining to P-immune sets, oracle separations, and the Berman-Hartmanis conjecture. We explain the phenomenon of unprovability in terms of both recursive properties of the formal systems J under consideration, and topological properties of complexity classes in a natural space which we call R. Provable properties correspond to closed sets of r. The topology provides geometric intuition for recognizing classes which are not closed in R, such as NPP (unless it is empty). We show how independence results follow immediately for these classes. In conclusion we argue that the type of independence result presented here forms an obstacle for day-to-day work in complexity theory, but does not bear directly on the possible independence of the P = NP question from Peano arithmetic or set theory. However, we believe our tools capable of measuring the link between the structure of a given language E ∉ P and the formal strength needed to prove the assertion ‘E ∉ P.’ Research in this direction has already been initiated by D. Joseph (J. Comput. System Sci. 25 (1983), 205–228).