โ Scribed by Lewis, F. D.
No coin nor oath required. For personal study only.
The study of Computational Complexity began with the investigatio~ of Turing machine computations with limits on the amounts of tape or time which could be used.
Latter a set of general axioms for measures of resource limiting was presented and this instigated much study of the properties of these general measures. Many interesting results were shown, but the general axioms allowed measures with undesirable properties and many attempts have been made to tighten up the axioms so that only desirable measures will be defined.
In this paper several undecidability aspects of complexity classes and several sets associated with them will be examined. These sets will be classified by their degree of unsolvability and restrictions will be placed on measures so that these degrees are identical.
This gives rise to a new crLterion for the "naturalness" of measures and to suggestions for strengthening the measures of complexity.
๐ SIMILAR VOLUMES