Diskussion:P (Komplexitätsklasse)

aus Wikipedia, der freien Enzyklopädie
Letzter Kommentar: vor 8 Jahren von Coenig in Abschnitt Sortierung ist kein Entscheidungsproblem
Zur Navigation springen Zur Suche springen

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)Beantworten