Hallo Leute,
hab in Sachen Komplexitätstheroie die Übersicht verloren. Also Wenn Problem M element von NP ist und B ist NP-vollständig, was genau heisst das dann???
Danke für die Hilfe
Hallo,
hab in Sachen Komplexitätstheroie die Übersicht verloren. Also
Wenn Problem M element von NP ist und B ist NP-vollständig,
was genau heisst das dann???
Wenn ein Problem NP-Vollständig ist, dann bedeutet das, dass alle anderen NP-Probleme auf diese Problem in Polynomialzeit reduzierbar sind.
In deinem konkreten Fall bedeutet das M