Algorithmen und Datenstrukturen · Senior · Frage 57 von 75
Was bedeutet es, dass ein Problem NP-vollständig ist?
- 1Es ist bewiesen, dass kein Algorithmus es lösen kann
- 2Es liegt in NP, und jedes NP-Problem ist polynomiell darauf reduzierbar
- 3Es lässt sich nur mit einem nichtdeterministischen Computer lösen
Antwort zeigen
Richtige Antwort: Es liegt in NP, und jedes NP-Problem ist polynomiell darauf reduzierbar
Erklärung
Lösungen lassen sich schnell prüfen, aber kein polynomieller Algorithmus zum Finden ist bekannt. Ein polynomieller Algorithmus für ein beliebiges NP-vollständiges Problem würde ganz NP lösen. Beispiele: SAT, Graphfärbung, Subset Sum.