Journal article 849 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!
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)$. Faculty of Science and Engineering 01 103 138