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

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Turing machines and related notions (03D10)

Related Items (41)

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

This page was built for publication: Tally languages and complexity classes