×

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


MSC:

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

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: 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: 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) · Zbl 0253.68020
[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: Addison-Wesley Reading, Mass · Zbl 0196.01701
[8] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Tatcher, J. W., In Complexity of Computer Computations (1972), Plenum Press: Plenum Press N.Y) · Zbl 0366.68041
[9] Knuth, D. E., The Art of Computer Programming, Vol. 3 (1973), Addison-Wesley: 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.; 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.