Tally languages and complexity classes

DOI10.1016/S0019-9958(74)90473-2zbMath0287.68029MaRDI QIDQ4775472

Ronald V. Book

Publication date: 1974

Published in: Information and Control (Search for Journal in Brave)

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

03D10: Turing machines and related notions

Related Items

Language classes defined by time-bounded relativised cellular automata, On the polynomial IO-complexity, On the computational complexity of membrane systems, Average-case intractability vs. worst-case intractability, Cook versus Karp-Levin: Separating completeness notions if NP is not small, A note on P-selective sets and closeness, On random reductions from sparse sets to tally sets, Minimal pairs for P, Downward translations of equality, A result relating disjunctive self-reducibility to P-immunity, Relations between average-case and worst-case complexity, Some observations on NP real numbers and P-selective sets, Reductions on NP and p-selective sets, On sparse sets in NP-P, Logarithmic advice classes, On being incoherent without being very hard, A positive relativization of polynomial time versus polylog space, Locating \(P\)/poly optimally in the extended low hierarchy, Computation times of NP sets of different densities, Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals, Optimal proof systems imply complete sets for promise classes, Tally NP sets and easy census functions., Sparse sets and collapse of complexity classes, One-way permutations and self-witnessing languages, NL-printable sets and nondeterministic Kolmogorov complexity, Reductions between disjoint NP-pairs, Upward separations and weaker hypotheses in resource-bounded measure, Classes of bounded nondeterminism, On intractability of the classUP, On polynomial-time truth-table reducibility of intractable sets to P-selective sets, On the definitions of some complexity classes of real numbers, Limitations of the upward separation technique, Inclusion complete tally languages and the Hartmanis-Berman conjecture, P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP, A Downward Collapse within the Polynomial Hierarchy