Computability and complexity. Foundations and tools for pursuing scientific applications

DOI10.1007/978-3-031-53744-8MaRDI QIDQ6549533zbMATH OpenFDO

Authors Rodney G. Downey

Publication date 3 June 2024

Published in Undergraduate Topics in Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational complexitylower boundsapproximation algorithmsNP-completenessfinite automataMinsky machinesPSPACE-completenesskernelizationregular languagesset theoryTuring machinesrecursion theoremaverage-case complexityTuring reducibilityLadner's theoremgeneric-case complexitypartial recursive functionsparametrised complexityuncountable setscountable setsoraclesarithmetic hierarchyundecidable problemsunsolvable word problemsGödel numbersSavitch's theoremdeeper computabilityparametric intractabilityparametrised tractabilitywait-and-see arguments

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Theory of computing (68Qxx) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Computability and recursion theory (03Dxx)

Recommendations

• scientific article; zbMATH DE number 5217263
• scientific article; zbMATH DE number 1052322
• Mathematics and computation. A theory revolutionizing technology and science
• Computational Complexity
• The nature of computation

Cited in

(1)

• Theoretical computer science: computational complexity

This page was built for publication: Computability and complexity. Foundations and tools for pursuing scientific applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6549533)