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 (9)

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

This page was built for publication: Inclusion complete tally languages and the Hartmanis-Berman conjecture