Complexity classes of provable recursive functions

摘要

Complexity measures and provable recursive functions (p-functions) are combined to define a p-measure as a measure for which Blum's axioms can be proved in a given axiomatic system. For p-measures, it is shown that the complexity class of a p-function contains only p-functions and that all p-functions form a single complexity class. Various other classes and a variation of a complexity measure, all suggested by the notion of provability, are also investigated. Classical results in complexity theory remain true when relativized to p-functions.