Abstract: My purpose in this lecture is to explain how the representation of algorithms by recursive programs can be used in complexity theory, especially in the derivation of lower bounds for worst-case time complexity, which apply to all—or, at least, a very large class of—algorithms. It may be argued that recursive programs are not a new computational paradigm, since their manifestation as Herbrand-Gödel-Kleene systems was present at the very beginning of the modern theory of computability, in 1934. But they have been dissed as tools for complexity analysis, and part of my mission here is to rehabilitate them.
Publication Year: 2005
Publication Date: 2005-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 5
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot