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 $\Sigma _{i+1}$. Dieses darf nicht auf $\Sigma _{i}$ basieren, da sonst die Hierarchie nicht aufgebaut wird. Es gilt schliesslich ${\mbox{NP}}^{\mbox{NP}}={\mbox{NP}}$

Richtig wäre: $\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 (ohne Benutzername signierter Beitrag von 141.89.226.146 (Diskussion) )

Einspruch: Die Behauptung ${\mbox{NP}}^{\mbox{NP}}={\mbox{NP}}$ ist wohl kaum bewiesen, wie man auf http://de.wikipedia.org/wiki/Orakel-Turingmaschine nachlesen kann. (nicht signierter Beitrag von 89.182.21.214 (Diskussion) 16:05, 20. Aug. 2010 (CEST))

Doch es ist so. In gewisser Weise kann man eine Orakel-TM als eine Art Unterprogramm, in der Abarbeitung die nach aussen die Kosten 1 hat, ansehen. Dabei ist das Unterprogramm nun ebenfalls in Polynomialzeit beschränkt. Selbst wenn das Programm nun polynomiell oft aufgerufen wird, wird die Gesamtausführungszeit immer noch Polynomiell sein.

Schaut man sich nun den Nichtdterminismus an. Die einfachste Betrachtung ist hier das Zeugnis. Es gibt für jedes Unterprogramm ein polynomielles Zeugnis. Die kann man nun wieder zusammen packen und erhält ein größerfes aber immer noch polynomielles Zeugnis.

Natürlich kann man die Klasse so aufschreiben, es gibt aber kein Problem, was in diese Klasse fallen wird. Das sieht man auch sehr gut, wnen man die Quantoren Schreibweisen für die Orakel TM verwendet. --Maria Siebert 22:58 19.10.2010 (ohne Benutzername signierter Beitrag von 92.225.104.224 (Diskussion) )

$\Sigma _{i+1}$ und $\Pi _{i+1}$-Orakel sind gleich mächtig: Man kann das eine durch das andere simulieren, indem man die Antwort des Orakels negiert. Deswegen stellt sich eigentlich gar nicht die Frage, ob $\Sigma _{i+1}={\mbox{NP}}^{\Sigma _{i}}$ oder $\Sigma _{i+1}={\mbox{NP}}^{\Pi _{i}}$. Die Definitionen sind nämlich äquivalent. Matzu (Diskussion) 11:13, 24. Nov. 2014 (CET)