Comparing complexity classes
Ronald V. Book · Journal of Computer and System Sciences · 1974
Cited by 49 works. doi:10.1016/s0022-0000(74)80008-5 Open-access PDF
Authors
References
- The complexity of theorem-proving procedures
- Alan Cobham. The intrinsic computational difficulty of functions. Logic, methodology and philosophy of science, Proceedings of the 1964 International Congress, edited by Yehoshua Bar-Hillel, Studies in logic and the foundations of mathematics, North-Holland Publishing Company, Amsterdam 1965, pp. 24–30.
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Theory of Recursive Functions and Effective Computability.
- On the Computational Complexity of Algorithms
- Relationships between nondeterministic and deterministic tape complexities
- Hierarchies of memory limited computations
- The equivalence problem for regular expressions with squaring requires exponential space
- The LBA Problem and its Importance in the Theory of Computing
- Currents in the theory of computing