### 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
(α)
.