No Cover Image

Conference Paper/Proceeding/Abstract 1609 views

A Characterisation of Definable NP Search Problems in Peano Arithmetic

Arnold Beckmann Orcid Logo

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

Swansea University Author: Arnold Beckmann Orcid Logo

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

Check full text

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
first_indexed 2013-07-23T11:49:24Z
last_indexed 2018-02-09T04:27:22Z
id cronfa54
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2013-10-17T11:44:34.9082771</datestamp><bib-version>v2</bib-version><id>54</id><entry>2012-02-23</entry><title>A Characterisation of Definable NP Search Problems in Peano Arithmetic</title><swanseaauthors><author><sid>1439ebd690110a50a797b7ec78cca600</sid><ORCID>0000-0001-7958-5790</ORCID><firstname>Arnold</firstname><surname>Beckmann</surname><name>Arnold Beckmann</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2012-02-23</date><deptcode>MACS</deptcode><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.</abstract><type>Conference Paper/Proceeding/Abstract</type><journal>Logic, Language, Information and Computation</journal><volume>5514</volume><journalNumber></journalNumber><paginationStart>1</paginationStart><paginationEnd>12</paginationEnd><publisher>Springer</publisher><placeOfPublication/><issnPrint>0302-9743</issnPrint><issnElectronic>1611-3349</issnElectronic><keywords/><publishedDay>1</publishedDay><publishedMonth>6</publishedMonth><publishedYear>2009</publishedYear><publishedDate>2009-06-01</publishedDate><doi>10.1007/978-3-642-02261-6_1</doi><url/><notes>In Logic, Language, Information and Computation, 16th International Workshop, WoLLIC 2009, Proceedings, Tokyo, Japan</notes><college>COLLEGE NANME</college><department>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</DepartmentCode><institution>Swansea University</institution><apcterm/><lastEdited>2013-10-17T11:44:34.9082771</lastEdited><Created>2012-02-23T17:02:01.0000000</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Arnold</firstname><surname>Beckmann</surname><orcid>0000-0001-7958-5790</orcid><order>1</order></author></authors><documents/><OutputDurs/></rfc1807>
spelling 2013-10-17T11:44:34.9082771 v2 54 2012-02-23 A Characterisation of Definable NP Search Problems in Peano Arithmetic 1439ebd690110a50a797b7ec78cca600 0000-0001-7958-5790 Arnold Beckmann Arnold Beckmann true false 2012-02-23 MACS 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. Conference Paper/Proceeding/Abstract Logic, Language, Information and Computation 5514 1 12 Springer 0302-9743 1611-3349 1 6 2009 2009-06-01 10.1007/978-3-642-02261-6_1 In Logic, Language, Information and Computation, 16th International Workshop, WoLLIC 2009, Proceedings, Tokyo, Japan COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University 2013-10-17T11:44:34.9082771 2012-02-23T17:02:01.0000000 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Arnold Beckmann 0000-0001-7958-5790 1
title A Characterisation of Definable NP Search Problems in Peano Arithmetic
spellingShingle A Characterisation of Definable NP Search Problems in Peano Arithmetic
Arnold Beckmann
title_short A Characterisation of Definable NP Search Problems in Peano Arithmetic
title_full A Characterisation of Definable NP Search Problems in Peano Arithmetic
title_fullStr A Characterisation of Definable NP Search Problems in Peano Arithmetic
title_full_unstemmed A Characterisation of Definable NP Search Problems in Peano Arithmetic
title_sort A Characterisation of Definable NP Search Problems in Peano Arithmetic
author_id_str_mv 1439ebd690110a50a797b7ec78cca600
author_id_fullname_str_mv 1439ebd690110a50a797b7ec78cca600_***_Arnold Beckmann
author Arnold Beckmann
author2 Arnold Beckmann
format Conference Paper/Proceeding/Abstract
container_title Logic, Language, Information and Computation
container_volume 5514
container_start_page 1
publishDate 2009
institution Swansea University
issn 0302-9743
1611-3349
doi_str_mv 10.1007/978-3-642-02261-6_1
publisher Springer
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
document_store_str 0
active_str 0
description 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_date 2009-06-01T04:29:42Z
_version_ 1851275380103577600
score 11.090362

Similar Items