Articles

GeeksforGeeks

by admin

Voraussetzung: NP-Vollständigkeit

NP-Problem:
Die NP-Probleme bestehen aus Problemen, deren Lösungen schwer zu finden, aber leicht zu überprüfen sind und von einer nicht deterministischen Maschine in Polynomzeit gelöst werden.

NP-Hartes Problem:
Ein Problem X ist NP-hart, wenn es ein NP-vollständiges Problem Y gibt, so dass Y in Polynomzeit auf X reduzierbar ist. NP-Harte Probleme sind so schwer wie NP-Vollständige Probleme. NP-Hartes Problem muss nicht in der NP-Klasse sein.

NP-Vollständiges Problem:

Ein Problem X ist NP-vollständig, wenn es ein NP-Problem Y gibt, so dass Y in Polynomzeit auf X reduzierbar ist. NP-Vollständige Probleme sind so schwer wie NP-Probleme. Ein Problem ist NP-Vollständig, wenn es Teil des NP- und NP-Hard-Problems ist. Eine nicht-deterministische Turing-Maschine kann NP-vollständige Probleme in Polynomzeit lösen.

Unterschied zwischen NP-Hard und NP-Complete:

NP-schwer NP-Vollständig
NP-Harte Probleme(z. B. X) können genau dann gelöst werden, wenn es ein NP-vollständiges Problem (z. B. Y) gibt, das in Polynomzeit auf X reduzierbar ist.NP-vollständige Probleme können durch einen annon-deterministischen Algorithmus / Turing-Maschine in Polynomzeit gelöst werden.
Um dieses Problem zu lösen, müssen Sie nicht in NP sein . Um dieses Problem zu lösen, müssen es sowohl NP- als auch NP-harte Probleme sein.
Do not have to be a Decision problem. It is exclusively a Decision problem.
Example: Halting problem, Vertex cover problem, Circuit-satisfiability problem, etc. Example: Determine whether a graph has a Hamiltonian cycle, Determine whether a Boolean formula is satisfiable or not, etc.