scientific article; zbMATH DE number 3873306

From MaRDI portal
Publication:3340841





[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.











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)