arnold beckmann's pages

Polynomial Local Search in the Polynomial Hierarchy and Witnessing in Fragments of Bounded Arithmetic

File: PDF-File

Author: Arnold Beckmann and Sam Buss
Title: Polynomial Local Search in the Polynomial Hierarchy and Witnessing in Fragments of Bounded Arithmetic
Journal: Journal of Mathematical Logic 2009, 9(1): 103-138
DOI: 10.1142/S0219061309000847

Abstract: The complexity class of Π 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 Σ b i - definable functions of T k+1 2 are characterized in terms of Π p k - PLS problems. These Π 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 Π 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 ∀Σ b 1 (α) - principle that is conjectured to separate T k 2 (α) and T k+1 2 (α) .

websites: Arnold Beckmann 2017-08-28 Valid HTML 4.01! Valid CSS!