Complexity classes of provable recursive functions |
| |
Authors: | Dan Gordon |
| |
Affiliation: | Departments of Mathematics and Computer Science, Purdue University, West Lafayette, Indiana 47907 USA |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|