Sei L NP-Vollständige Sprache und L wird durch DTM in n^log(n) Zeit entschieden. Gilt dann P=NP?
Hossa Grußloser 
Wenn du für ein Problem der NP-vollständigen Probleme einen Algorithmus findest, der in polynomialer Laufzeit eine Lösung findet, kannst du diesen Algortithmus aus alle NP-vollständigen Probleme anwenden. Zustäzlich wäre gezeigt, dass alle nicht-deterministisch polynomialen (NP) Probleme in polynomialer Laufzeit lösbar sind, dass also NP=P gilt.
Sei L NP-Vollständige Sprache und L wird durch DTM in
n^log(n) Zeit entschieden. Gilt dann P=NP?
Hier würde ein NP-vollständiges Problem L in polynomialer Laufzeit n*log(n) gelöst. Es wäre dann NP=P.
Viele Grüße
Hasenfuß
Hallo.
Sei L NP-Vollständige Sprache und L wird durch DTM in
n^log(n) Zeit entschieden. Gilt dann P=NP?Hier würde ein NP-vollständiges Problem L in polynomialer
Laufzeit n*log(n) gelöst. Es wäre dann NP=P.
Das Ursprungsposting sprach von n^log(n) und nicht von n*log(n). Somit wäre das keine polynomiale Laufzeit und P=NP wäre damit nicht bewiesen.
Sebastian.
Du hast Recht und ich brauche wohl eine neue Brille
Viele Grüße
Hasenfuß
jo danke vielen vielen dank,
habe noch mal nachgefragt bei meinem prof und ihr habt recht.
vielen dank und viele grüße
sebastian