A finite model-theoretical proof of a property of bounded query classes within PH

Kołodziejczyk, Leszek Aleksander

J. Symbolic Logic, Tome 69 (2004) no. 1, p. 1105-1116 / Harvested from Project Euclid

Résumé

We use finite model theory (in particular, the method of FM-truth definitions, introduced in [MM01] and developed in [K04], and a normal form result akin to those of [Ste93] and [G97]) to prove: ¶ Let m ≥ 2. Then: ¶ (A) If there exists k such that NP ⊆ σ_mTIME(n^k) ∩ Π_mTIME(n^k), then for every r there exists k_r such that P^{NP[n^r]} ⊆ σ_mTIME(n^k_r) ∩ Π_mTIME(n^k_r); ¶ (B) If there exists a superpolynomial time-constructible function f such that NTIME(f) ⊆ Σ^p_m ∪ Π^p_m, then additionally P^{NP[n^r]} ⊈ Σ^p_m ∪ Π^p_m. ¶ This strengthens a result by Mocas [M96] that for any r, P^{NP[n^r]} ⊈ NEXP. ¶ In addition, we use FM-truth definitions to give a simple sufficient condition for the σ¹₁ arity hierarchy to be strict over finite models.

Publié le : 2004-12-14
Classification:

@article{1102022213,
     author = {Ko\l odziejczyk, Leszek Aleksander},
     title = {A finite model-theoretical proof of a property of bounded query classes within PH},
     journal = {J. Symbolic Logic},
     volume = {69},
     number = {1},
     year = {2004},
     pages = { 1105-1116},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1102022213}
}

Kołodziejczyk, Leszek Aleksander. A finite model-theoretical proof of a property of bounded query classes within PH. J. Symbolic Logic, Tome 69 (2004) no. 1, pp.  1105-1116. http://gdmltest.u-ga.fr/item/1102022213/