A comparison of polynomial time reducibilities. (English) Zbl 0321.68039


68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[2] Cook, S. A., The complexity of theorem-proving procedures, Third annual ACM Symposium on Theory of Computing (1971) · Zbl 0363.68125
[3] Hopcroft, J. E.; Ullman, J. D., Formal Languages and Their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0196.01701
[4] Jones, N. D., Reducibility among combinatorial problems in log n space, Proc. of Seventh Annual Princeton Conference on Information Sciences and Systems (1973)
[5] Karp, R. M., Reducibility among combinatorial problems, (Miller; Thatcher, Complexity of Computer Computations (1973), Plenum Press: Plenum Press New York) · Zbl 0366.68041
[6] Ladner, R. E., On the structure of polynomial time reducibility, J. ACM, 22 (1975) · Zbl 0322.68028
[7] Lynch, N. A., Relativization of the theory of computational complexity, (Ph. D. Thesis (1972), M.I.T) · Zbl 0353.68059
[9] Meyer, A. R.; Stockmeyer, L. J., The equivalence problem for regular expressions with squaring requires exponential space, 13th Annual IEEE Symposium of Switching and Automata Theory (1972)
[10] Meyer, A. R.; Stockmeyer, L. J., Word problems requiring exponential time, Fifth Annual Symposium on Theory of Computing (1973) · Zbl 0359.68050
[11] Post, E. L., Recursively enumerable sets of positive integers and their decision problems, Bull. AMS, 50 (1944) · Zbl 0063.06328
[12] Rogers, M., Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill: McGraw-Hill New York · Zbl 0183.01401
[13] Savage, J. E., Computational work and time on finite machines, J. ACM, 9, 4 (1972) · Zbl 0251.68031
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.