The quantifier structure of sentences that characterize nondeterministic time complexity
From MaRDI portal
Publication:1198956
DOI10.1007/BF01276438zbMath0752.68040MaRDI QIDQ1198956
Publication date: 16 January 1993
Published in: Computational Complexity (Search for Journal in Brave)
Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (3)
The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey ⋮ Linear time and the power of one first-order universal quantifier ⋮ On the expressive power of monadic least fixed point logic
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds for recognizing small cliques on CRCW PRAM's
- 0-1 laws and decision problems for fragments of second-order logic
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- An application of games to the completeness problem for formalized theories
- Parity, circuits, and the polynomial-time hierarchy
- The Spectra of First-Order Sentences and Computational Complexity
- A Nontrivial Lower Bound for an NP Problem on Automata
- Reachability is harder for directed than for undirected finite graphs
- Universal quantifiers and time complexity of random access machines
- Second-order and Inductive Definability on Finite Structures
- Complexity classes and theories of finite models
- Asymptotic probabilities of existential second-order Gödel sentences
- Monadic generalized spectra
- Turing machines and the spectra of first-order formulas
This page was built for publication: The quantifier structure of sentences that characterize nondeterministic time complexity
