caa a22 4500 469033886 CHVBK 20180323132751.0 cr unu---uuuuu 170328e19920301xx s 000 0 eng 10.1007/BF01276438 doi (NATIONALLICENCE)springer-10.1007/BF01276438 Lynch James Department of Mathematics and Computer Science, Clarkson University, 13699-5815, Potsdam, NY, USA aut The quantifier structure of sentences that characterize nondeterministic time complexity [Elektronische Daten] [James Lynch] For every nondeterministic Turing machineM of time complexityT(n), there is a second-order sentence σ of a very restricted form, whose set of finite models encodes the set of strings recognized byM. Specifically, σ has a relational symbol which is interpreted as addition restricted to finite segments of the natural numbers, and a prefix consisting of existentially quantified unary second-order variables followed by a universal-existential first-order part. Here, every input stringx is encoded by a model of sizeT(|x|). Using a closely related encoding of strings as models where the size of the model is the length of the string, a consequence is that ifT(n)=n d, then there is a sentence with a similar prefix but whose second-order variables ared-ary and whose finite models encode the strings accepted byM. Potential applications to low-level complexity are discussed. Birkhäuser Verlag, 1992 nondeterministic time complexity nationallicence finite models nationallicence secondorder logic nationallicence 68Q15 nationallicence 03C13 nationallicence computational complexity Birkhäuser-Verlag 2/1(1992-03-01), 40-66 1016-3328 2:1<40 1992 2 37 https://doi.org/10.1007/BF01276438 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01276438 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Lynch James Department of Mathematics and Computer Science, Clarkson University, 13699-5815, Potsdam, NY, USA aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag 2/1(1992-03-01), 40-66 1016-3328 2:1<40 1992 2 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer