Inclusion complete tally languages and the Hartmanis-Berman conjecture

DOI10.1007/BF01768464zbMath0365.68044OpenAlexW2024969746WikidataQ123127225 ScholiaQ123127225MaRDI QIDQ4140380

Selman, Alan L., Ronald V. Book, David P. Dobkin, Celia Wrathall

Publication date: 1977

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01768464

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

A complexity theory for feasible closure properties, Expressing uniformity via oracles, On polynomial-time truth-table reducibility of intractable sets to P-selective sets, Reductions on NP and p-selective sets, Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis, On sparse sets in NP-P, The complexity of unions of disjoint sets, P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP, A low and a high hierarchy within NP

Cites Work

• Unnamed Item
• A comparison of polynomial time reducibilities
• Translational lemmas, polynomial time, and \((\log n)^j\)-space
• Comparing complexity classes
• Relationships between nondeterministic and deterministic tape complexities
• On the Structure of Polynomial Time Reducibility
• P-Complete Approximation Problems
• Tally languages and complexity classes
• Turing machines and the spectra of first-order formulas
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers