A complexity-theoretic proof of a Recursion-Theoretic Theorem
Abstract
It is well known that Complexity Theory inherited many tools from Recursion Theory. This note is an example where tools from Complexity Theory simplify the proof of a Recursion Theoretical result, illustrating the value of mingling the two subjects.
References
[1]
Jones, Neil D. (1997) Computability and Complexity. MIT Press, Cambridge, Mass., 1997.
[2]
Li, Ming and Vitányi, Paul (1997) An Introduction to Kolmogorov Complexity and Its Applications. 2nd ed., Springer-Verlag, New York, 1997.
[3]
Soare, Robert I. (1987) Recursively Enumerable Sets and Degrees. Springer-Verlag, Berlin 1987.
- A complexity-theoretic proof of a Recursion-Theoretic Theorem
Recommendations
Recursion Theoretic Operators for Function Complexity Classes
We characterize the gap between time and space complexity of functions by operators and completeness. First, we introduce a new notion of operators for function complexity classes based on recursive function theory and construct an operator which ...
On graph-theoretic lemmata and complexity classes
SFCS '90: Proceedings of the 31st Annual Symposium on Foundations of Computer ScienceSeveral new complexity classes of search problems that lie between the classes FP and FNP are defined. These classes are contained in the class TFNP of search problems that always have a solution. A problem in each of these new classes is defined in ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2004 Author.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 June 2004
Published in SIGACT Volume 35, Issue 2
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 193Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in