Weak cardinality theorems
From MaRDI portal
Publication:5718691
DOI10.2178/jsl/1122038917zbMath1092.03020OpenAlexW2072890682MaRDI QIDQ5718691
Publication date: 16 January 2006
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2178/jsl/1122038917
Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The strong exponential hierarchy collapses
- Comparing verboseness for finite automata and Turing machines
- \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- Bounded queries in recursion theory
- Enumerative counting is hard
- A structural property of regular frequency computations.
- Nondeterministic Space is Closed under Complementation
- Frequency computations and the cardinality theorem
- A Downward Collapse within the Polynomial Hierarchy
- Effective Search Problems
- A cardinality version of Beigel's nonspeedup theorem
- Concatenation as a basis for arithmetic
This page was built for publication: Weak cardinality theorems