Diskussion:P (Komplexitätsklasse)
Letzter Kommentar: vor 8 Jahren von Coenig in Abschnitt Sortierung ist kein Entscheidungsproblem
P ist in polynomialer Zeit entscheidbar, wo hingegen NP mit gegebenem Zertifikat in polynomialer Zeit verifizierbar ist! NP ist nicht in pol. Zeit entscheidbar! -- 17:14, 12. Jan. 2008 (CET)
Das entscheidbar bezieht sich aber auf die Deterministische Turingmaschine - die Aussage ist also soweit richtig. (nicht signierter Beitrag von 85.178.191.150 (Diskussion) 01:26, 4. Jul 2011 (CEST))
Sortierung ist kein Entscheidungsproblem
[Quelltext bearbeiten]P wird oben nur für Entscheidungsprobleme definiert. Später wird aber das Sortierproblem als Beispiel aufgeführt. Das ist zumindest ungenau. --Coenig (Diskussion) 11:09, 16. Apr. 2016 (CEST)