Journal of the ACM Bibliography

Additional Key Words and Phrases: polynomial time computation, Turing reducibility, many-one reducibility

Selected papers that cite this one

• R. Beigel and J. Goldsmith. Downard separation fails castastrophically for limited nondeterminism classes. SIAM Journal on Computing, 27(5):1420-1429, October 1998.

• Ronald V. Book. On languages reducible to algorithmically random languages. SIAM Journal on Computing, 23(6):1275-1282, December 1994.

• Ronald V. Book and Celia Wrathall. On languages specified by relative acceptance. Theoretical Computer Science, 7(2):185-195, October 1978.

• Bernd Borchert and Riccardo Silvestri. A characterization of the leaf language classes. Information Processing Letters, 63(3):153-158, 14 August 1997.

• Harry Buhrman, Albrecht Hoene, and Leen Torenvliet. Splittings, robustness, and structure of complete sets. SIAM Journal on Computing, 27(3):637-653, June 1998.

• Peter Bürgisser. On the structure of Valiant's complexity classes. In 15th Annual Symposium on Theoretical Aspects of Computer Science, volume 1373 of Lecture Notes in Computer Science, pages 194-204, Paris France, 25-27 February 1998. Springer.

• Rod G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness I: Basic results. SIAM Journal on Computing, 24(4):873-921, August 1995.

• Rod Downey and Richard A. Shore. Degree theoretic definitions of the low_2 recursively enumerable sets. The Journal of Symbolic Logic, 60(3):727-756, September 1995.

• Shimon Even, Timothy J. Long, and Yacov Yacobi. A note on deterministic and nondeterministic time complexity. Information and Control, 55(1-3):117-124, October/November/December 1982.

• Shimon Even, Alan L. Selman, and Yacov Yacobi. The complexity of promise problems with applications to public-key cryptography. Information and Control, 61(2):159-173, May 1984.

• Stephen Fenner, Lance Fortnow, and Lide Li. Gap-definability as a closure property. Information and Computation, 130(1):1-17, 10 October 1996.

• Christine Ann Haught and Theodore A. Slaman. Automorphisms in the PTIME-Turing degrees of recursive sets. Annals of Pure and Applied Logic, 84(1):139-152, 6 March 1997.

• Lane A. Hemaspaandra and Leen Torenvliet. Optimal advice. Theoretical Computer Science, 154(2):367-377, 5 February 1996. Note.

• Maren Hinrichs and Gerd Wechsung. Time bounded frequency computations. Information and Computation, 139(2):234-257, 15 December 1997.

• Sanjeev Khanna, Madhu Sudan, and David P. Williamson. A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 11-20, El Paso, Texas, 4-6 May 1997.

• R. E. Ladner, N. A. Lynch, and A. L. Selman. A comparison of polynomial time reducibilities. Theoretical Computer Science, 1(2):103-123, December 1975.

• Nancy Lynch. Log space machines with mutliple oracle tapes. Theoretical Computer Science, 6(1):25-39, February 1978.

• Michael Machtey. Minimal pairs of polynomial degrees with subexponential complexity. Theoretical Computer Science, 2(1):73-76, June 1976.

• Pavel Pudlák and F. N. Springsteel. Complexity in mechanized hypothesis formation. Theoretical Computer Science, 8(2):203-225, April 1979.

• Kenneth W. Regan. Diagonalization, uniformity, and fixed-point theorems. Information and Computation, 98(1):1-40, May 1992.

• Kenneth W. Regan and Heribert Vollmer. Gap-languages and log-time complexity classes. Theoretical Computer Science, 188(1-2):101-116, 30 November 1997.

• Alan L. Selman. Analogues of semicursive sets and effective reducibilities to the study of NP complexity. Information and Control, 52(1):36-51, January 1982.

• Juichi Shinoda. Strong polynomial-time reducibility. Annals of Pure and Applied Logic, 84(1):97-117, 6 March 1997.

• Mike Townsend. A polynomial jump operator. Information and Control, 68(1-3):146-169, January/February/March 1986.

Selected references

• A. Borodin, R. L. Constable, and J. E. Hopcroft. Dense and non-dense families of complexity classes. In Conference Record of 1969 Tenth Annual Symposium on Switching and Automata Theory, pages 7-19, Waterloo, Ontario, Canada, 15-17 October 1969. IEEE.

• Stephen A. Cook. The complexity of theorem-proving procedures. In Conference Record of Third Annual ACM Symposium on Theory of Computing, pages 151-158, Shaker Heights, Ohio, 3-5 1971 1971.

• Richard Ladner, Nancy Lynch, and Alan Selman. Comparisons of polynomial-time reducibilities. In Conference Record of Sixth Annual ACM Symposium on Theory of Computing, pages 110-121, Seattle, Washington, 30 April-2 May 1974.

• Michael Machtey. Classification of computable functions by primitive recursive classes. In Conference Record of Third Annual ACM Symposium on Theory of Computing, pages 251-257, Shaker Heights, Ohio, 3-5 1971 1971.

• Michael Machtey. The honest subrecursive classes are a lattice. Information and Control, 24(3):247-263, March 1974.

• Ravi Sethi. Complete register allocation problems. In Conference Record of Fifth Annual ACM Symposium on Theory of Computing, pages 182-195, Austin, Texas, 30 April-2 May 1973.

• L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time: Preliminary report. In Conference Record of Fifth Annual ACM Symposium on Theory of Computing, pages 1-9, Austin, Texas, 30 April-2 May 1973.

Shortcuts: