ECCC-Report TR03-051https://eccc.weizmann.ac.il/report/2003/051Comments and Revisions published for TR03-051en-usMon, 30 Jun 2003 18:14:49 +0300
Paper TR03-051
| The Relative Complexity of Local Search Heuristics and the Iteration Principle |
Tsuyoshi Morioka
https://eccc.weizmann.ac.il/report/2003/051Johnson, 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.
Mon, 30 Jun 2003 18:14:49 +0300https://eccc.weizmann.ac.il/report/2003/051