A hybrid algorithm is a collection of heuristics, paired with a polynomial time selector S that runs on the input to decide which heuristic should be executed to solve the problem. Hybrid algorithms are of particular interest in scenarios where the selector must decide between heuristics that are" good" with respect to different complexity measures.

We focus on hybrid algorithms with a" hardnessdefying" property: for a problem II, there is a set of complexity measures {m} whereby II is known or conjectured to be unsolvable for each mi, but for each heuristic h₂ of the hybrid algorithm, one can give a complexity guarantee for h; on the instances of II that S selects for h; that is strictly better than mi. More concretely, we show that for several NP-hard problems, a given instance can either be solved exactly with substantially improved runtime (eg 20 (n)), or be approximated in polynomial time with an approximation ratio exceed ing that of the known or conjectured inapproximability of the problem, assuming PNP.