arnold beckmann
A Characterisation of Definable NP Search Problems in Peano Arithmetic
Logic, Language, Information and Computation. 16th International Workshop, WoLLIC 2009, Tokyo, Japan, June 21-24, 2009. Pages: 1 - 12
Publication year: 2009
The complexity class of $\prec$-bounded local search problems with goals is introduced for well-orderings $\prec$, and is used to give a characterisation of definable NP search problems in Peano Arithmetic.