scientific article; zbMATH DE number 3873306
[For the entire collection see Zbl 0538.00005.] The spectrum of a first-order sentence (with equality and order \(<)\) is the set of cardinalities of its finite models (where \(<\) is interpreted by linear order). Let S\(p(d\forall,funct)\) (resp. \(Sp(d\forall,k-ary funct))\) denote the class of spectra of sentences with at most d universal quantifiers and with function symbols (resp. which are at most k-ary). Let \(Sp(d\forall,k-ary rel)\) be the similar class for sentences without function symbols but with relation symbols at most k-ary. A set of positive integers is in NTIME(T(n)) (resp. NRAM(T(n))) if it is accepted by a nondeterministic Turing machine (resp. nondeterministic RAM where the only arithmetical operation is incrementation by one) in time T(n) where n is the input integer. Using the inclusion \(NTIME(T \log T)\subset\cup_{c}NRAM(cT)\) shown by B. Monien, we prove that for each integer \(d\geq 1:\) \[ (1)\quad NTIME(n^ d \log n)\subset\cup_{c}NRAM(cn^ d)= \] \[ Sp(d\forall,funct)=Sp(d\forall,d-ary funct)\subset NTIME(n^ d(\log n)^ 2) \] and for \(d\geq 2\), \[ (2)\quad NTIME(n^ d)\subset\cup_{c}NRAM(cn^ d/\log n)\subset Sp((d+1)\forall,d-ary rel) \] and \[ (3)\quad NTIME(n^{d-\epsilon})\subset Sp(d\forall,d-ary rel) \] for each real number \(\epsilon >0.\) By the hierarchy theorem of NTIME classes, (1) and (3) imply: \[ (4)\quad Sp(d\forall,d-ary funct)\subsetneqq Sp((d+1)\forall,(d+1)-ary rel)\quad for\quad d\geq 1. \] Similar results hold for generalized spectra and alternating spectra. Inclusions (1) and (4) (resp. (2)) refine results of P. Pudlák (resp. J. F. Lynch). Note that (2) and (3) are not proved in our paper.
- Generic oracles, uniform machines, and codes
- The quantifier structure of sentences that characterize nondeterministic time complexity
- Universal Turing machines with complexity constraint
- A dichotomy result for Ramsey quantifiers
- The Spectra of First-Order Sentences and Computational Complexity
- scientific article; zbMATH DE number 3873293 (Why is no real title available?)
- scientific article; zbMATH DE number 3878906 (Why is no real title available?)
- COMPLETE SECOND ORDER SPECTRA
- Universal quantifiers and time complexity of random access machines
- scientific article; zbMATH DE number 3961589 (Why is no real title available?)
- scientific article; zbMATH DE number 7029312 (Why is no real title available?)
- scientific article; zbMATH DE number 3997169 (Why is no real title available?)
- A generalized quantifier concept in computational complexity theory
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3340841)