Diskussion:Polynomialzeithierarchie

Das ist erst der Anfang...

Das Thema Komplexität ist in der deutschsprachigen Wikipedia noch arg unterrepräsentiert. Dies sind die ersten Zeilen des englischen Artikels, der als Übersetzung hier Eingang finden könnte.

Ich habe mal einiges ergänzt, jedoch weist der Artikel immer noch Lücken auf. Mit der (informellen) Beschreibung von Orakelmaschinen bin ich nicht zufrieden und möglicherweise gibt es noch weitere Sätze über die PH. Möglicherweise könnte der Begriff der Orakelmaschinen auch in einem eigenen Artikel erklärt werden (wenn es nicht schon einen gibt - auf die Schnelle hab ich keinen gefunden). Mathias 10:45, 18. Jun 2006 (CEST)

Letzteres ist getan: Orakel-Turingmaschine --Florian Seffler 17:40, 1. Dez. 2006 (CET)

Die Definition der Polynomialzeithierachie ist fehlerhaft. Dre Fehler ist in der Definition von ${\displaystyle \Sigma _{i+1}}${\displaystyle \Sigma _{i+1}}. Dieses darf nicht auf ${\displaystyle \Sigma _{i}}${\displaystyle \Sigma _{i}} basieren, da sonst die Hierarchie nicht aufgebaut wird. Es gilt schliesslich ${\displaystyle {\mbox{NP}}^{\mbox{NP}}={\mbox{NP}}}${\displaystyle {\mbox{NP}}^{\mbox{NP}}={\mbox{NP}}}

Richtig wäre: ${\displaystyle \Sigma _{i+1}={\mbox{NP}}^{\Pi _{i}}}${\displaystyle \Sigma _{i+1}={\mbox{NP}}^{\Pi _{i}}}. Nur dann baut sich die gewünschte Hierarchie auf.

Anscheinend zieht sich der Fehler durch viele Fachbücher. --Maria Siebert 17.32 21.07.2010