Abstract: Conventional complexity theory refines computability theory. Total recursive word functions f : Σ* → Σ* or recursive subsets X ⊆ Σ* are classified with respect to the resource which machines need to compute or decide them, respectively. By means of notations complexity can be transferred to other sets. Complexity theory has grown to an extensive field with numerous important results.
Publication Year: 2000
Publication Date: 2000-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 26
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot