P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- 1 December 1979
- journal article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 13 (1), 55-65
- https://doi.org/10.1007/bf01744288
Abstract
No abstract availableThis publication has 13 references indexed in Scilit:
- Inclusion complete tally languages and the Hartmanis-Berman conjectureTheory of Computing Systems, 1977
- A comparison of polynomial time reducibilitiesTheoretical Computer Science, 1975
- On the Structure of Polynomial Time ReducibilityJournal of the ACM, 1975
- Tally languages and complexity classesInformation and Control, 1974
- Comparing complexity classesJournal of Computer and System Sciences, 1974
- Turing machines and the spectra of first-order formulasThe Journal of Symbolic Logic, 1974
- On Languages Accepted in Polynomial TimeSIAM Journal on Computing, 1972
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- Characterizations of Pushdown Machines in Terms of Time-Bounded ComputersJournal of the ACM, 1971
- Semirecursive sets and positive reducibilityTransactions of the American Mathematical Society, 1968