Conference Paper/Proceeding/Abstract 1125 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.
DOI (Published version): 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.
| 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: |
Faculty of Science and Engineering |
| Start Page: |
1 |
| End Page: |
12 |