Limits of computation. An introduction to the undecidable and the intractable

MaRDI QIDQ4897685zbMATH OpenFDO

Authors Edna E. Reiter, Clayton Matthew Johnson

Publication date 27 December 2012

zbMATH Keywords

complexityNP-completenessundecidabilityintractabilitycomputability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Computability and complexity theory.
• What can be computed? A practical guide to the theory of computation
• Limits of computation. From a programming perspective
• scientific article; zbMATH DE number 3909745
• Basic course theoretical computer science with exercises and test questions.

Cited in

(9)

• scientific article; zbMATH DE number 3827200 (Why is no real title available?)
• Limits of computation. From a programming perspective
• The golden ticket. P, NP, and the search for the impossible
• Can a free market be complete?
• scientific article; zbMATH DE number 2123258 (Why is no real title available?)
• What can be computed? A practical guide to the theory of computation
• Computability. Logic, reasoning, computer and Assembler, infinity, limits of automatizability. Textbook for class-room and self-study
• From heaps of matches to the limits of computability
• Tractability. Practical approaches to hard problems

This page was built for publication: Limits of computation. An introduction to the undecidable and the intractable

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