/ en / Traditional / help

Beats Biblionetz - Texte

NP-vollständige Probleme

Zu finden in: The New Turing Omnibus (Seite 386 bis 391), 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

Zur Zeit weiß man von über 2000 Problemen, daß sie NP-vollständig sind (vgl. Kapitel 41). Seit 1972, als Stephen Cook feststellte, daß das Erfüllbarkeitsproblem NP-vollständig ist, haben Wissenschaftler einen ständigen Strom von Ergebnissen veröffentlicht, in denen die NP-Vollständigkeit für andere Probleme gezeigt wird. Die Liste NP-vollständiger Probleme wächst ständig.

Von A. K. Dewdney im Buch The New Turing Omnibus (2001) im Text NP-vollständige Probleme

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ändige Probleme: Artikel als Volltext bei Springerlink (lokal: PDF, 827 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.