Universality, Reducibility, and Completeness

DOI10.1007/978-3-540-74593-8_3zbMATH Open1211.68197OpenAlexW1830422832MaRDI QIDQ3608467FDOQ3608467

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

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

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)

Cited In (2)

• Title not available (Why is that?)
• 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)