WorksComputer Science
The Metacomplexity Structure of Search Problems
Abstract
We study the metacomplexity tasks of refuting an algorithm for a given search problem or refuting a mapping reduction between two search problems. We show that these tasks are deeply related to the structure of the lattice of search problems under mapping reductions: the "refutation of a reduction" task amounts to a certain Heyting-type arrow in this lattice. We then give several structural complexity results about search problems and show they have implications for metacomplexity. First, by relating metacomplexity to a Heyting algebra structure, we are able to translate results from intuitionistic logic into complexity theoretic consequences. For example, the propositional logic identity translates to the following complexity-theoretic fact: if a search problem reduces to both and to the refutation task of , then is in . All such logical identities that hold in intuitionistic logic translate to complexity in a black box way. We find prime ideals of the reducibility lattice of search problems; as a consequence, we show that for any verifiable search problem , either is in or else the refutation task of is in . Similarly, either has infinitely-often heuristic algorithms or else the refutation task of has infinitely often heuristic algorithms. Finally, we give a structural result that may be of independent interest: any "tamely semantic" class of search problems (one which can be enumerated using a Halting oracle) is characterized by its decidably verifiable hard problems.