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.

websites: Arnold Beckmann 2017-08-28 Valid HTML 4.01! Valid CSS!