No Cover Image

Journal article 530 views

POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC / Arnold Beckmann; SAMUEL R. BUSS

Journal of Mathematical Logic, Volume: 09, Issue: 01, Pages: 103 - 138

Swansea University Author: Arnold, Beckmann

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

Abstract

The complexity class of $Pi^p_k$-polynomial local search (PLS) problems is introduced and is used to give new witnessing theorems for fragments of bounded arithmetic. For 1≤i≤k+1, the $Sigma^p_i$-definable functions of $T^{k+1}_2$ are characterized in terms of $\Pi^p_k$-PLS problems. These $\Pi^p_k$...

Full description

Published in: Journal of Mathematical Logic
ISSN: 0219-0613
Published: 2009
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa5269
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2013-07-23T11:52:08Z
last_indexed 2018-02-09T04:31:26Z
id cronfa5269
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2015-06-30T20:37:11.5743429</datestamp><bib-version>v2</bib-version><id>5269</id><entry>2012-02-23</entry><title>POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED 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>SCS</deptcode><abstract>The complexity class of $Pi^p_k$-polynomial local search (PLS) problems is introduced and is used to give new witnessing theorems for fragments of bounded arithmetic. For 1&#x2264;i&#x2264;k+1, the $Sigma^p_i$-definable functions of $T^{k+1}_2$ are characterized in terms of $\Pi^p_k$-PLS problems. These $\Pi^p_k$-PLS problems can be defined in a weak base theory such as $S^1_2$, and proved to be total in $T^{k+1}_2$. Furthermore, the $\Pi^p_k$-PLS definitions can be skolemized with simple polynomial time functions, and the witnessing theorem itself can be formalized, and skolemized, in a weak base theory. We introduce a new $\forall \Sigma^b_1(\alpha)$-principle that is conjectured to separate $T^k_2(\alpha)$ and $T^{k+1}_2(\alpha)$.</abstract><type>Journal Article</type><journal>Journal of Mathematical Logic</journal><volume>09</volume><journalNumber>01</journalNumber><paginationStart>103</paginationStart><paginationEnd>138</paginationEnd><publisher/><issnPrint>0219-0613</issnPrint><issnElectronic/><keywords/><publishedDay>30</publishedDay><publishedMonth>9</publishedMonth><publishedYear>2009</publishedYear><publishedDate>2009-09-30</publishedDate><doi>10.1142/S0219061309000847</doi><url/><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><lastEdited>2015-06-30T20:37:11.5743429</lastEdited><Created>2012-02-23T17:02:01.0000000</Created><path><level id="1">College of Science</level><level id="2">Computer Science</level></path><authors><author><firstname>Arnold</firstname><surname>Beckmann</surname><orcid>0000-0001-7958-5790</orcid><order>1</order></author><author><firstname>SAMUEL R.</firstname><surname>BUSS</surname><order>2</order></author></authors><documents/><OutputDurs/></rfc1807>
spelling 2015-06-30T20:37:11.5743429 v2 5269 2012-02-23 POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC 1439ebd690110a50a797b7ec78cca600 0000-0001-7958-5790 Arnold Beckmann Arnold Beckmann true false 2012-02-23 SCS The complexity class of $Pi^p_k$-polynomial local search (PLS) problems is introduced and is used to give new witnessing theorems for fragments of bounded arithmetic. For 1≤i≤k+1, the $Sigma^p_i$-definable functions of $T^{k+1}_2$ are characterized in terms of $\Pi^p_k$-PLS problems. These $\Pi^p_k$-PLS problems can be defined in a weak base theory such as $S^1_2$, and proved to be total in $T^{k+1}_2$. Furthermore, the $\Pi^p_k$-PLS definitions can be skolemized with simple polynomial time functions, and the witnessing theorem itself can be formalized, and skolemized, in a weak base theory. We introduce a new $\forall \Sigma^b_1(\alpha)$-principle that is conjectured to separate $T^k_2(\alpha)$ and $T^{k+1}_2(\alpha)$. Journal Article Journal of Mathematical Logic 09 01 103 138 0219-0613 30 9 2009 2009-09-30 10.1142/S0219061309000847 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2015-06-30T20:37:11.5743429 2012-02-23T17:02:01.0000000 College of Science Computer Science Arnold Beckmann 0000-0001-7958-5790 1 SAMUEL R. BUSS 2
title POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
spellingShingle POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
Arnold, Beckmann
title_short POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
title_full POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
title_fullStr POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
title_full_unstemmed POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
title_sort POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
author_id_str_mv 1439ebd690110a50a797b7ec78cca600
author_id_fullname_str_mv 1439ebd690110a50a797b7ec78cca600_***_Arnold, Beckmann
author Arnold, Beckmann
author2 Arnold Beckmann
SAMUEL R. BUSS
format Journal article
container_title Journal of Mathematical Logic
container_volume 09
container_issue 01
container_start_page 103
publishDate 2009
institution Swansea University
issn 0219-0613
doi_str_mv 10.1142/S0219061309000847
college_str College of Science
hierarchytype
hierarchy_top_id collegeofscience
hierarchy_top_title College of Science
hierarchy_parent_id collegeofscience
hierarchy_parent_title College of Science
department_str Computer Science{{{_:::_}}}College of Science{{{_:::_}}}Computer Science
document_store_str 0
active_str 0
description The complexity class of $Pi^p_k$-polynomial local search (PLS) problems is introduced and is used to give new witnessing theorems for fragments of bounded arithmetic. For 1≤i≤k+1, the $Sigma^p_i$-definable functions of $T^{k+1}_2$ are characterized in terms of $\Pi^p_k$-PLS problems. These $\Pi^p_k$-PLS problems can be defined in a weak base theory such as $S^1_2$, and proved to be total in $T^{k+1}_2$. Furthermore, the $\Pi^p_k$-PLS definitions can be skolemized with simple polynomial time functions, and the witnessing theorem itself can be formalized, and skolemized, in a weak base theory. We introduce a new $\forall \Sigma^b_1(\alpha)$-principle that is conjectured to separate $T^k_2(\alpha)$ and $T^{k+1}_2(\alpha)$.
published_date 2009-09-30T03:15:05Z
_version_ 1685025252067770368
score 10.76741