The quantifier structure of sentences that characterize nondeterministic time complexity

DOI10.1007/BF01276438MaRDI QIDQ1198956zbMATH OpenFDO

Authors James Lynch

Publication date 16 January 1993

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01276438

zbMATH Keywords

finite modelsnondeterministic time complexitysecond-order logic

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The Spectra of First-Order Sentences and Computational Complexity
• scientific article; zbMATH DE number 17544
• Descriptive characterizations of computational complexity
• scientific article; zbMATH DE number 1304315
• scientific article; zbMATH DE number 3873306

Cites work

• 0-1 laws and decision problems for fragments of second-order logic
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• A Nontrivial Lower Bound for an NP Problem on Automata
• An application of games to the completeness problem for formalized theories
• Asymptotic probabilities of existential second-order Gödel sentences
• Complexity classes and theories of finite models
• scientific article; zbMATH DE number 3938569 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 4114587 (Why is no real title available?)
• Lower bounds for recognizing small cliques on CRCW PRAM's
• Monadic generalized spectra
• Parity, circuits, and the polynomial-time hierarchy
• Reachability is harder for directed than for undirected finite graphs
• Second-order and Inductive Definability on Finite Structures
• The Spectra of First-Order Sentences and Computational Complexity
• Turing machines and the spectra of first-order formulas
• Universal quantifiers and time complexity of random access machines

Cited in

(5)

• Linear time and the power of one first-order universal quantifier
• A nonasymptotic lower time bound for a strictly bounded second-order arithmetic
• scientific article; zbMATH DE number 4170888 (Why is no real title available?)
• The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey
• On the expressive power of monadic least fixed point logic

This page was built for publication: The quantifier structure of sentences that characterize nondeterministic time complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1198956)