Weak cardinality theorems
From MaRDI portal
Publication:5718691
DOI10.2178/jsl/1122038917zbMath1092.03020MaRDI 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
03D05: Automata and formal grammars in connection with logical questions
03D10: Turing machines and related notions
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