Tsuyoshi Morioka

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 >>>

Albert Atserias, Neil Thapen

The ordering principle states that every finite linear order has a least element. We show that, in the relativized setting, the surjective weak pigeonhole principle for polynomial time functions does not prove a Herbrandized version of the ordering principle over $\mathrm{T}^1_2$. This answers an open question raised in [Buss, Ko{\l}odziejczyk ... more >>>