ENDEXTENSIONS IN BOUNDED ARITHMETIC AND COMPUTATIONAL COMPLEXITY

Masahiro Yasumoto Graduate School of Human Informatics Nagoya University

Abstract. Let N be an elementary extension of ℕ and n ∈ N −ℕ. We prove that P T C(n) has no proper endextension of Δ_{1}^{b}-LLIND and consider conditions that a model of bounded arithmetic has a proper end extension.

Let N be an elementary extension of the set of natural numbers ℕ and M be a substructure of N which is a model of P A^{−}, then M has a proper endextension of P A^{−}. If M satisfies P A, then it is well known that M also has a proper endextension of P A. In this paper, we consider conditions that a model M of a theory T in bounded arithmetic has a proper endextension of some subtheory of T.

Typeset by AMS-TEX 2 MASAHIRO YASUMOTO

This research is partially supported by Grant-in-Aid for Scientific Research(No.12640115), Ministry of Education, Science and Culture of Japan.

1. Polynomial time closure Let n be a nonstandard element i.e. n ∈ N − ℕ. P T C(n) denotes the polynomial time closure of {n} in N, then P T C(n) is a model of T_{2}^{0}. If P = NP, then P T C(n) is a model of S_{2}. In this section, we prove Theorem 1. P T C(n) has no proper endextension which satisfies Δ_{1}^{b} − LLIND.

Let T (e, x; α) be an oracle Turing machine satisfying the condition that for any oracle Turing machine T′(x; α) there are infinitely many natural numbers e such that

T (e, x; α) = T′(x; α).

Let T (e, x; α)(t) denote the content of the output tape of the machine T at the time t of the computation with an input x. Then y = T (e, x; α)(|z|) can be written as a Δ_{1}^{b}(α)-formula which we write by

y = {e}(x, |z|; α).

The polynomial time closure P T C(n) of {n} is the set

{{e}(n, |n|^{|e|}; ∅)| e ∈ ℕ}. Assume that P T C(n) has a proper endextension L of Δ_{1}^{b} − LLIND. Let m ∈

L − P T C(n). Since L is an endextension of P T C(n), for all e ∈ ℕ we have m > 2^{|n|^{e}} ∈

ENDEXTENSIONS IN BOUNDED ARITHMETIC AND COMPUTATIONAL COMPLEXITY 3

P T C(n). Now we consider the following infinite set

α = {x ∈ P T C(n) | x < |n|}.

Since L is an endextension of P T C(n), α is defined in L by a Δ_{1}^{b}-formula with the parameters n and m, i.e.

α ={x ∈ L | L ⊧ x < |n| ∧ x = {e}(n, |n|^{|e|}; ∅) for some e ∈ ℕ }
={x ∈ L | L ⊧ x < |n| ∧ ∃e < ||m||(x = {e}(n, |n|^{|e|}; ∅) ∧ ∀y < e(x ≠ {y}(n, |n|^{|y|}; ∅)))}.

Then ℕ is defined in L by a Δ_{1}^{b}-formula with parameters n and m,

ℕ = {e ∈ L | L ⊧ e < ||m||∧∃x < |n|(x = {e}(n, |n|^{|e|}; ∅)∧∀y < e(x ≠ {y}(n, |n|^{|y|}; ∅)))}

Let Φ(e, m, n) be the defining Δ_{1}^{b}-formula of ℕ in L, then LLIND(Φ(x, m, n)) does not hold in L.

4 MASAHIRO YASUMOTO

2. Endextensions In this section, we try to construct an endextension L of P T C(n) which contains 2^{n}. Since ∃x(x = 2^{n}) holds in L but not in P T C(n), L cannot be an elementary extension of P T C(n). So many tools in model theory, omitting type arguments, internal ultrapower etc. which give endextensions are of no use. Let M = {x ∈ N | x < y for some y ∈ P T C(n)}. Then M is closed under the smash function, hence M is a model of S_{2}.

First we define L to be the set of all bounded subsets of P T C(n) defined by Σ^{b}- formulas, in other words, α ∈ L if and only if there exists a Σ^{b}-formula Φ(x, y) and a ∈ P T C(n) such that

α = {x ∈ P T C(n) | P T C(n) ⊧ Φ(x, a) ∧ x < a}.

For such α, Φ(x, y) and a ∈ P T C(n), let

α_{M} = {x ∈ M | M ⊧ Φ(x, a) ∧ x < a}.

If P = NP, then P T C(n) is a Σ^{b}-elementary substructure of M, hence α = α_{M} ∩ P T C(n). Since α_{M} is definable in N, there exists a c_{α} ∈ N such that

α_{M} = {x ∈ N | bit(c_{α}, x) = 1}.

By identifying α ∈ L with c_{α}, we can consider L ⊂ N. Let α = {n } ∈ L, then c_{α} = 2^{n}, so L contains 2^{n}.

ENDEXTENSIONS IN BOUNDED ARITHMETIC AND COMPUTATIONAL COMPLEXITY 5

Lemma 1. If P = NP, then L is an endextension of P T C(n). Proof. Let c_{α} ∈ L. Then there is a Σ^{b}-formula Φ(x, y) and a a ∈ P T C(n) ⊂ M such that α = {x ∈ P T C(n) | P T C(n) ⊧ Φ(x, a) ∧ x < a}. Let b ∈ P T C(n) be such that c_{α} < b, then we have

α = {x ∈ P T C(n) | P T C(n) ⊧ Φ(x, a) ∧ x < |b|}.

Since we are assuming P = NP, P T C(n) is a model of S_{2}, hence c_{α} ∈ P T C(n). Lemma 2. If P = NP, then α ∈ L implies ⌊\frac{1}{2}α⌋ ∈ L. Proof. Let Φ(x, y) and a ∈ P T C(n) define α, i.e.

α = {x ∈ P T C(n) | P T C(n) ⊧ Φ(x, a) ∧ x < a},

then

⌊\frac{1}{2}α⌋ = \{x ∈ P T C(n) | P T C(n) ⊧ Φ(x + 1, a) ∧ x < a − 1\}.

Lemma 3. If P = NP, then α, β ∈ L implies α♯β ∈ L. Proof. Let Φ(x, y) and a ∈ P T C(n) (resp. Ψ(x, y) and b ∈ P T C(n)) define α (resp. β),

6 MASAHIRO YASUMOTO

then

α♯β = {x ∈ P T C(n) | P T C(n) ⊧ x = max(α) + max(β)}
= {x ∈ P T C(n) | P T C(n) ⊧ ∃y < a∃z < b(x = y + z ∧ Φ(y) ∧ Ψ(z)
∧∀v < a(y < v → ¬Φ(v)) ∧ ∀w < b(z < w → ¬Ψ(w)) ∧ x < a + b}.

Lemma 4. If P = NP, then α, β ∈ L implies α + β ∈ L. Proof. Let Φ(x, y), Ψ(x, y) and a, b ∈ P T C(n) be as in the proof of Lemma 3. Then α + β is defined by the following bounded formula and max(a, b) + 1.

((Φ(x, y)△Ψ(x, y)) ∧ ∃i < x(¬Φ(i, y) ∧ ¬Ψ(i, y) ∧ ∀j < x(i < j → (Φ(j, y)△Ψ(j, y)))))

∨(¬(Φ(x, y)△Ψ(x, y)) ∧ ∃i < x(Φ(i, y) ∧ Ψ(i, y) ∧ ∀j < x(i < j → (Φ(j, y)△Ψ(j, y)))))

where Φ△Ψ denotes (Φ ∧ ¬Ψ) ∨ (¬Φ ∧ Ψ).

Next we consider multiplication on L. To prove that L is closed under multiplication, we need more assumption than P = NP. Lemma 5. Assume that P = PSPACE, then α, β ∈ L implies α · β ∈ L. Proof. α · β is computable by a PSPACE machine with oracles α and β, more precisely, there exists an oracle PSPACE-machine S(x; α, β) such that

x ∈ α · β if and only if S(x; α, β).

ENDEXTENSIONS IN BOUNDED ARITHMETIC AND COMPUTATIONAL COMPLEXITY 7

Since α, β ∈ L and P = PSPACE, S(x, α, β) is poly-time computable, hence α · β ∈ L.

Lemma 6. Assume that P = PSPACE, then L is a model of Σ_{0}^{b} − LIND.

Proof. Let Φ(x) be a Σ_{0}^{b}-formura, then there is a Σ_{0}^{1,b} formula ϕ(x) such that

L ⊧ Φ(x) if and only if P T C(n) ⊧ ϕ(x).

Assume that P T C(n) ⊧ ϕ(0) ∧ ¬ϕ(t) for some t ∈ P T C(n). Since we are assuming

P = PSPACE, we can find x ∈ P T C(n) by a PSPACE-machine such that P T C(n) ⊧

ϕ(x) ∧ ¬ϕ(x + 1), as contended.

Conjecture. Assume that P = PSPACE, then L is a model of Δ_{1}^{b} − LLIND.

If we prove the Conjecture, then by Theorem 1, we can conclude P ≠ PSPACE.

References

1. P.Hajek and P. Pudlak, Metamathematics of First-Order Arithmetic, Springer-Verlag, 1993.

2. G.Takeuti and M.Yasuoto, Forcing on Bounded Arithmetic, Gödel’96 (P.Hájek, eds.), Lecture Notes in Logic 6 (1996), pp. 120-138.

3. G.Takeuti and M.Yasuoto, Forcing on Bounded Arithmetic II, Journal of Symbolic Logic 63 (1998), pp. 860-868.

Masahiro Yasumoto Graduate School of Human Informatics Nagoya University Chikusa-ku, Nagoya, 464-8601, JAPAN

     E-mail address: yasumoto@info.human.nagoya-u.ac.jp