No Cover Image

Conference Paper/Proceeding/Abstract 581 views

A Characterisation of Definable NP Search Problems in Peano Arithmetic / Arnold Beckmann

Logic, Language, Information and Computation, Volume: 5514, Pages: 1 - 12

Swansea University Author: Arnold, Beckmann

Full text not available from this repository: check for access using links below.

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.

Published in: Logic, Language, Information and Computation
ISSN: 0302-9743 1611-3349
Published: Springer 2009
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa54
Tags: Add Tag
No Tags, Be the first to tag this record!
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.
Item Description: In Logic, Language, Information and Computation, 16th International Workshop, WoLLIC 2009, Proceedings, Tokyo, Japan
College: College of Science
Start Page: 1
End Page: 12