Relative complexity of checking and evaluating. (English) Zbl 0342.68028


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


[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, Mass · Zbl 0207.01701
[2] Aho, A.V.; Ullman, J.D., The theory of parsing translation, and compiling, Bol. 1, (1972), Prentice-Hall Englewood Cliffs, N.J, Parsing · Zbl 0264.68032
[3] Baker, T.; Gill, J.; Solovay, R., Relativizations of the P=? NP question, SIAM J. computing, 431-442, (1975) · Zbl 0323.68033
[4] Cook, S.A., The complexity of theorem proving procedures, Proc. 3rd ACM symp. on theory of computing, 151-158, (1971)
[5] Hardy, G.H.; Wright, E.M., An introduction to the theory of numbers, (1960), Oxford University Press · Zbl 0086.25803
[6] Hartmanis, J.; Stearns, R.E., On the computational complexity of algorithms, Trans. amer. math. soc., 117, 285-306, (1965) · Zbl 0131.15404
[7] Hopcroft, J.E.; Ullman, J.D., Formal languages and their relation to automata, (1969), Addison-Wesley Reading, Mass · Zbl 0196.01701
[8] Karp, R.M., Reducibility among combinatorial problems, () · Zbl 0366.68041
[9] Knuth, D.E., The art of computer programming, Vol. 3, (1973), Addison-Wesley Reading, Mass · Zbl 0191.17903
[10] Edmonds, J., Minimum partition of a matroid into independent subsets, J. res. nat. bureau stand., B69, 67-72, (1965) · Zbl 0192.09101
[11] Rabin, M.O., Proving simultaneous positivity of linear forms, JCSS 6, 639-650, (1972) · Zbl 0274.68022
[12] L.G. Valiant, General context-free recognition in less than cubic time, JCSS, to appear. · Zbl 0312.68042
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.