### arnold beckmann's pages

## A Characterisation of Definable NP
Search Problems in Peano Arithmetic

**File:** PDF-File

**Author:** Arnold Beckmann

**Title:** A Characterisation of Definable NP
Search Problems in Peano Arithmetic

**Proceedings:** Logic, Language, Information and Computation.
16th International Workshop, WoLLIC 2009, Tokyo, Japan, June 21-24, 2009.

**Pages:** 1 - 12

**DOI:** 10.1007/978-3-642-02261-6_1

**Abstract:**
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.