Inhaltsverzeichnis:
- Definition - Was bedeutet nicht deterministische Polynomzeit (NP)?
- Techopedia erklärt nicht deterministische Polynomzeit (NP)
Definition - Was bedeutet nicht deterministische Polynomzeit (NP)?
Die nichtdeterministische Polynomzeit (NP) ist eigentlich ein Marker, der verwendet wird, um auf eine Reihe von Problemen und Grenzen der Leistungsfähigkeit bestimmter Arten von Berechnungen hinzuweisen. NP bezieht sich auf die Menge von Problemen, die in der Polynomzeit durch eine nicht deterministische Turing-Maschine gelöst werden können.
Techopedia erklärt nicht deterministische Polynomzeit (NP)
Die nicht deterministische Polynomzeit basiert auf der Phrase "Polynomzeit", die angibt, ob ein Algorithmus innerhalb bestimmter Grenzen, die für die Geschwindigkeit relevant sind, arbeiten kann. Die Polynomialzeit wurde entwickelt, um über die Machbarkeit der Arbeit und Entwicklung von Algorithmen zu sprechen.
Wenn sich ein Problem in einer nicht deterministischen Polynomzeit befindet, kann die nicht deterministische Turing-Maschine zuerst die Lösung erraten und dann einen überprüfbaren Algorithmus ausführen, der bestätigt, ob diese Vermutung korrekt war oder nicht. Verifiziererbasierte Definitions- oder Maschinendefinitionsprogramme testen im Wesentlichen die anfänglichen Auswahlmöglichkeiten der nicht deterministischen Turing-Maschine, um die Ergebnisse zu verifizieren.
All dies ist eine hoch theoretische Rechenstruktur. Während maschinelles Lernen Fortschritte über deterministische Systeme hinaus erzielt hat, steckt die Idee, nicht deterministische Entscheidungen zu überprüfen, noch in den Kinderschuhen. Suchen Sie nach mehr Entwicklung auf dieser Grenze der Datenverarbeitung.
