Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
6. Nondeterminism and NP-Completeness
verfasst von : Steven Homer, Alan L. Selman
Erschienen in: Computability and Complexity Theory
Verlag: Springer US
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Several different additions to the basic deterministic Turing machine model are often considered. These additions add computational power to the model and so allow us to compute certain problems more efficiently. Often these are important problems with seemingly no efficient solution in the basic model. The question then becomes whether the efficiency the additional power provides is really due to the new model or whether the added efficiency could have been attained without the additional resources.