/ en / Traditional / help

Beats Biblionetz - Texte

NP-Vollständigkeit

Zu finden in: The New Turing Omnibus (Seite 297 bis 303), 2001  local web 
Erste Seite des Textes (PDF-Thumbnail)
Dieses Biblionetz-Objekt existiert erst seit März 2021. Es ist deshalb gut möglich, dass viele der eigentlich vorhandenen Vernetzungen zu älteren Biblionetz-Objekten bisher nicht erstellt wurden. Somit kann es sein, dass diese Seite sehr lückenhaft ist.

iconZusammenfassungen

A. K. Dewdney

Der Ausdruck NP-vollständig wird häufig benutzt aber nicht immer richtig verstanden. Wenn man es praktisch betrachtet, handelt es sich bei einem NP-vollständigen Problem um eine Aufgabe, die man auf dem Computer nur dann lösen kann, wenn man bereit ist, außergewöhnlich lange Zeit auf ihre Lösung zu warten. Theoretisch kann man ein NP-vollständiges Problem am besten als eine Anwendung des Satzes von Cook verstehen. Das erste NP-vollständige Problem, die Erfüllbarkeit (vgl. Kapitel 34), wurde 1970 von Stephen Cook während der Fertigstellung seiner Dissertation in Informatik an der Universität von Kalifornien in Berkeley gefunden. Cook entdeckte eine allgemeine Transformation, die jedes Problem einer bestimmten großen, NP genannten Klasse auf ein einziges Problem der Logik abbildet, das Erfüllbarkeitsproblem (SAT)1 genannt wird (Abbildung 41.1).

Von A. K. Dewdney im Buch The New Turing Omnibus (2001) im Text NP-Vollständigkeit

iconDieses Kapitel erwähnt ...


Begriffe
KB IB clear
NP, NP-completeNP-complete

iconDieses Kapitel  erwähnt vermutlich nicht ... Eine statistisch erstelle Liste von nicht erwähnten (oder zumindest nicht erfassten) Begriffen, die aufgrund der erwähnten Begriffe eine hohe Wahrscheinlichkeit aufweisen, erwähnt zu werden.

icon
Nicht erwähnte Begriffe
P (PTIME)

iconTagcloud

iconAnderswo finden

icon

iconVolltext dieses Dokuments

LokalAuf dem WWW NP-Vollständigkeit: Artikel als Volltext bei Springerlink (lokal: PDF, 952 kByte; WWW: Link OK )

iconAnderswo suchen  Auch im Biblionetz finden Sie nicht alles. Aus diesem Grund bietet das Biblionetz bereits ausgefüllte Suchformulare für verschiedene Suchdienste an. Biblionetztreffer werden dabei ausgeschlossen.

iconBiblionetz-History Dies ist eine graphische Darstellung, wann wie viele Verweise von und zu diesem Objekt ins Biblionetz eingetragen wurden und wie oft die Seite abgerufen wurde.