Journal article 598 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:

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$...

Full description

Published in: Journal of Mathematical Logic 0219-0613 2009 https://cronfa.swan.ac.uk/Record/cronfa5269 No Tags, Be the first to tag this record!
first_indexed 2013-07-23T11:52:08Z 2018-02-09T04:31:26Z cronfa5269 SURis 2015-06-30T20:37:11.5743429v252692012-02-23POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC1439ebd690110a50a797b7ec78cca6000000-0001-7958-5790ArnoldBeckmannArnold Beckmanntruefalse2012-02-23SCSThe 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 ArticleJournal of Mathematical Logic09011031380219-061330920092009-09-3010.1142/S0219061309000847COLLEGE NANMEComputer ScienceCOLLEGE CODESCSSwansea University2015-06-30T20:37:11.57434292012-02-23T17:02:01.0000000College of ScienceComputer ScienceArnoldBeckmann0000-0001-7958-57901SAMUEL R.BUSS2 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 POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC Arnold, Beckmann POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC 1439ebd690110a50a797b7ec78cca600 1439ebd690110a50a797b7ec78cca600_***_Arnold, Beckmann Arnold, Beckmann Arnold Beckmann SAMUEL R. BUSS Journal article Journal of Mathematical Logic 09 01 103 2009 Swansea University 0219-0613 10.1142/S0219061309000847 College of Science collegeofscience College of Science collegeofscience College of Science Computer Science{{{_:::_}}}College of Science{{{_:::_}}}Computer Science 0 0 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)$. 2009-09-30T03:14:54Z 1706764737375633408 10.809259