Journal article 1143 views
POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
Arnold Beckmann 
,
SAMUEL R. BUSS
,
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.
DOI (Published version): 10.1142/S0219061309000847
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$...
| 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≤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)$.</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><apcterm/><lastEdited>2015-06-30T20:37:11.5743429</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><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 Faculty of Science and Engineering School of Mathematics and Computer 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 |
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 $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:06:19Z |
| _version_ |
1763749689054724096 |
| score |
11.014291 |