A finite model-theoretical proof of a property of bounded query classes within PH
Leszek Aleksander Kołodziejczyk · Journal of Symbolic Logic · 2004
Abstract. 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⊆ Σm TIME(nk)∩ Πm TIME(nk), then for every r there exists kr such that : (B) If there exists a superpolynomial time-constructible function f such that NTIME(f) , then additionally . This strengthens a result by Mocas [M96] that for any r, . In addition, we use FM-truth definitions to give a simple sufficient condition for the arity hierarchy to be strict over finite models.