×
Selman, Alan L.

P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP. (English) Zbl 0405.03018

Math. Syst. Theory 13, 55-65 (1979).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0405.03018

Cited in 59 Documents

MSC:

03D30 Other degrees and reducibilities in computability and recursion theory
03D15 Complexity of computation (including implicit computational complexity)
68Q25 Analysis of algorithms and problem complexity

Keywords:

Turing Reducibility; Selective Sets; Tally Languages; Polynomial Ti
PDF BibTeX XML Cite
\textit{A. L. Selman}, Math. Syst. Theory 13, 55--65 (1979; Zbl 0405.03018)
Full Text: DOI

References:

[1] R. Book, On languages accepted in polynomial time,SIAM J. Comput. 1 281–287 (1972). · Zbl 0251.68042
[2] R. Book, Tally languages and complexity classes,Information and Control 26 186–193 (1974). · Zbl 0287.68029
[3] R. Book, Comparing complexity classes,J. Computer System Sci. 9 213–229 (1974). · Zbl 0331.02020
[4] R. Book, C. Wrathall, A. Selman, and D. Dobkin, Inclusion complete tally languages and the Hartmanis-Berman conjecture,Math. Systems Theory 11 1–8 (1977). · Zbl 0365.68044
[5] S. Cook, The complexity of theorem-proving procedures, Third annual ACM Symposium on Theory of Computing 151–158 (1971). · Zbl 0253.68020
[6] S. Cook, Characterizations of pushdown machines in terms of time-bounded computers,J. Assoc. Comput. Mach. 18 4–18 (1971). · Zbl 0222.02035
[7] C. Jockusch, Semirecursive sets and positive reducibility,Trans. Amer. Math. Soc. 131 420–436 (1968). · Zbl 0198.32402
[8] N. Jones and A. Selman, Turing machines and the spectra of first-order formulas,J. Symbolic Logic 29 139–150 (1974). · Zbl 0288.02021
[9] R. Karp, Reducibility among combinatorial problems,Complexity of Computer Computations, R. Miller and J. Thatcher, eds., Plenum Press, New York, 85–103 (1972).
[10] R. Karp, Combinatories= ? linear programming + number theory, Project MAC Workshop on Complexity Computations 1973.
[11] R. Ladner, On the structure of polynomial time reducibility,J. Assoc. Comput. Mach. 22 155–171 (1975). · Zbl 0322.68028
[12] R. Ladner, N. Lynch, and A. Selman, A comparison of polynomial time reducibilities,Theoretical Computer Sci. 1 103–123 (1975). · Zbl 0321.68039
[13] V. Pratt, Every prime has a succinct certificate,SIAM J. Comput. 4 214–220 (1975). · Zbl 0316.68031
[14] I. Simon and J. Gill, Polynomial reducibilities and upward diagonalizations, Ninth annual ACM Symposium on Theory of Computing 186–194 (1977).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.