Abstract:
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, we obtain the first relative separation of $\PLS$ from Papadimitriou's classes $\PPA$, $\PPAD$, $\PPADS$, and $\PPP$. Based on the criterion, we derive a special case of Riis's \emph{independence criterion} for the Bounded Arithmetic theory $S^2_2(L)$. We also prove that $\PLS$ is closed under Turing reducibility.