The quantifier structure of sentences that characterize nondeterministic time complexity (Q1198956): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+\(\Sigma_ 1^ 1\)-formulae on finite structures
@@ Property / cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures / rank @@
+Normal rank
@@ Property / cites work @@
+Reachability is harder for directed than for undirected finite graphs
+Normal rank
@@ Property / cites work @@
+Lower bounds for recognizing small cliques on CRCW PRAM's
+Normal rank
@@ Property / cites work @@
+An application of games to the completeness problem for formalized theories
+Normal rank
@@ Property / cites work @@
+Monadic generalized spectra
@@ Property / cites work: Monadic generalized spectra / rank @@
+Normal rank
@@ Property / cites work @@
+Parity, circuits, and the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+The Spectra of First-Order Sentences and Computational Complexity
+Normal rank
@@ Property / cites work @@
+Universal quantifiers and time complexity of random access machines
+Normal rank
@@ Property / cites work @@
+A Nontrivial Lower Bound for an NP Problem on Automata
+Normal rank
@@ Property / cites work @@
+Q3862379
@@ Property / cites work: Q3862379 / rank @@
+Normal rank
@@ Property / cites work @@
+Turing machines and the spectra of first-order formulas
+Normal rank
@@ Property / cites work @@
+-1 laws and decision problems for fragments of second-order logic
+Normal rank
@@ Property / cites work @@
+Complexity classes and theories of finite models
@@ Property / cites work: Complexity classes and theories of finite models / rank @@
+Normal rank
@@ Property / cites work @@
+Q4729754
@@ Property / cites work: Q4729754 / rank @@
+Normal rank
@@ Property / cites work @@
+Asymptotic probabilities of existential second-order Gödel sentences
+Normal rank
@@ Property / cites work @@
+Second-order and Inductive Definability on Finite Structures
+Normal rank
@@ Property / cites work @@
+Q3709896
@@ Property / cites work: Q3709896 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:1198956