Johnson, Papadimitriou and Yannakakis introduce the class \PLS
consisting of optimization problems for which efficient local-
search heuristics exist. We formulate a type-2 problem \iter
that characterizes \PLS in style of Beame et al., and prove
a criterion for type-2 problems to be nonreducible to \iter.
As a corollary, ... more >>>