No Cover Image

Journal article 523 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!
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)$.
College: College of Science
Issue: 01
Start Page: 103
End Page: 138