streng NP-vollständiges Problem - Lexikon der Mathematik

Lexikon der Mathematik: streng NP-vollständiges Problem

ein Problem, das für ein Polynom p bei Beschränkung auf Eingaben, die bei Länge n nur durch p(n) beschränkte Zahlen enthalten, NP-vollständig ist.

Falls NP≠P (NP-Vollständigkeit) ist, gibt es für streng NP-vollständige Probleme keine Algorithmen, die eine pseudopolynomielle Rechenzeit haben.

Copyright Springer Verlag GmbH Deutschland 2017

Die Autoren

- Prof. Dr. Guido Walz

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Artikel zum Thema

Die fabelhafte Welt der Mathematik: Wie zwei Mathematiker die Zukunft berechenbar machten

Was passiert, wenn ein Glücksspiel plötzlich endet? Diese vor 400 Jahren gestellte Frage begründete die Wahrscheinlichkeitstheorie – und ist bis heute relevant.

Netzwerke: Der Algorithmus, der alle Erwartungen sprengte

Nach 100 Jahren brachte ein ungewöhnlicher Ansatz einen Durchbruch, an den viele nicht mehr glaubten: Ein Algorithmus bietet extrem schnell Lösungen für komplexe Netzwerke.

Freistetters Formelwelt: Von einfachen Grenzwerten zu Schwarzen Löchern

Grenzen können nicht nur aus politischer, sondern auch aus mathematischer Sicht schwierig werden. Auf die Astronomie angewendet nehmen sie sogar eine philosophische Dimension an.

Die fabelhafte Welt der Mathematik: Schokolinsen sorgten für eine mathematische Überraschung

Ein 200-Liter-Fass voller M&M's-Schokolinsen: Was eigentlich als harmloser Streich gedacht war, führte zu überraschenden Forschungsergebnissen in der Geometrie.

Themenkanäle

Die neue Generation von Computern

Erste Prototypen von Quantencomputern gibt es bereits. Was wird sich mit den Prozessoren ändern, die auf Quantenmechanik basieren? Sind Daten dann noch sicher? Eine Themenseite

Quantenphysik

Die Quantenphysik ist neben der Relativitätstheorie eine der Säulen der modernen Physik - mit Auswirkungen bis in die Philosophie.

Das Digital-Manifest

Algorithmen, Nudging, Big Data - unser Leben wird zunehmend digitaler. Doch viele Menschen sind darauf nicht vorbereitet. Daher benötigen wir klare Regeln. Ein Appell.

SponsoredPartnerinhalte