Universality, Reducibility, and Completeness

DOI10.1007/978-3-540-74593-8_3MaRDI QIDQ3608467zbMATH OpenOpenAlexFDO

Authors Mark Burgin

Publication date 5 March 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74593-8_3

zbMATH Keywords

algorithmreducibilitycomputabilityuniversalcomputing powerproblem hardnessproblem completeness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Turing machines and related notions (03D10) General topics in the theory of algorithms (68W01)

Recommendations

• scientific article; zbMATH DE number 3858462
• scientific article; zbMATH DE number 2150282
• Some considerations on universality
• Fine hierarchies and m-reducibilities in theoretical computer science
• scientific article; zbMATH DE number 2154080

Cited in

(2)

• scientific article; zbMATH DE number 3858462 (Why is no real title available?)
• The universal complementation property

This page was built for publication: Universality, Reducibility, and Completeness

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