betaFeedback

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 x∧¬x=⊥x\wedge \neg x=\bot translates to the following complexity-theoretic fact: if a search problem RR reduces to both SS and to the refutation task of SS, then RR is in FP\mathsf{FP}. 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 SS, either SS is in (FP/poly)io(\mathsf{FP/poly})_{io} or else the refutation task of SS is in (FP/poly)io(\mathsf{FP/poly})_{io}. Similarly, either SS has infinitely-often heuristic algorithms or else the refutation task of SS 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.

Paper details

vlnc:W_7s6x2hhx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT 5.4, Gemini 3.0 pro, AI

View statement
Looking for related papers…