Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

Becks

Praktikant

  • "Becks" started this thread

Posts: 5

Date of registration: Oct 2nd 2009

1

Thursday, April 10th 2014, 11:25am

Komplexitätstheorie

Hallo,

ich habe nächste Woche meine Prüfung in Komplexitätstheorie und bin mir etwas unsicher wie detailliert man Beweise aus der Vorlesung und Übung können muss. Kann mir jemand sagen worauf Prof. Vollmer in mündlichen Prüfungen (speziell in Komplexitätstheorie) wert legt? Mehr auf grundlegende Konzepte und Theoreme oder auch auf Beweise von diesen?

Falls jemand alte Prüfungsprotokolle oder Erfahrungsberichte hat würde ich mich auch sehr freuen wenn ich diese bekommen könnte.
  • Send private message

nano

Alter Hase

  • "nano" is male

Posts: 146

Date of registration: Oct 11th 2010

Location: Hannover

Occupation: THI

2

Thursday, April 10th 2014, 11:56am

Wichtige Theoreme und auch die Beweise dazu, aber nur, wenn man sich auch recht leicht was unter den Beweisen vorstellen kann. Nichts, was im Skript nur langes Umformen von Gleichungen war. Ich musste z.B. die Vollständigkeitsbeweise von QBF und QBF-k wissen, man sollte aber z.B. auch die einzelnen Teile des Satzes von Toda kennen.
Kapitel 4 wurde übrigens in der Vorlesung nicht behandelt.
  • Send private message

Becks

Praktikant

  • "Becks" started this thread

Posts: 5

Date of registration: Oct 2nd 2009

3

Thursday, April 10th 2014, 3:47pm

Quoted from "nano"

Wichtige Theoreme und auch die Beweise dazu, aber nur, wenn man sich auch recht leicht was unter den Beweisen vorstellen kann. Nichts, was im Skript nur langes Umformen von Gleichungen war. Ich musste z.B. die Vollständigkeitsbeweise von QBF und QBF-k wissen, man sollte aber z.B. auch die einzelnen Teile des Satzes von Toda kennen.
Kapitel 4 wurde übrigens in der Vorlesung nicht behandelt.
Danke, das hat mir schonmal sehr weitergeholfen. Falls sich noch jemand an seine Prüfung erinnern kann, wäre ich über weitere Rückmeldungen sehr dankbar!
  • Send private message

Anselm

borlark

Posts: 164

Date of registration: Oct 13th 2010

Occupation: WiMi ThI

4

Thursday, April 10th 2014, 5:14pm

Man muss eigentlich immer nen großes Bild malen mit den ganzen vorkommenden Komplexitätsklassen (PH inkl. den unteren Ebenen der Sigma, Pi und Delta-Klassen, PSPACE, die verschiedenen probabilistischen Klassen, ParityP, P^PP = P^ParityP), dabei natürlich die Inklusionen einzeichnen und sagen welche Klassen unter Vereinigung, Schnitt und Komplement abgeschlossen sind und was vollständige Probleme für die Klassen sind (falls es welche gibt/falls welche bekannt sind). Weiterhin werden dann noch so ~2-3 größere Beweise gefragt. Zum Beispiel warum QBF vollständig für PSPACE ist, warum OLMS vollständig für Delta_p^2. Generell halt einfach mal zu einigen der gezeichneten oder gesagten Sachen (Abschlusseigenschaften, vollständige Probleme, Inklusionen) sagen, warum sie gelten. Dabei schon den Beweis komplett umreißen, aber wie nano schon schrieb: keine langen Rechnugen. Was noch gerne dran kommt: Beweis für P^PP = P^ParityP (hatte zumindest Julian mal in der Übung gesagt) und auch Parity.ParityP = ParityP oder ParityP^ParityP = ParityP.
(wobei das ja eher kürzere Beweise sind).

Gruß,
Anselm
"Once you figure out what a joke everything is, being the comedian's the only thing makes sense."
~The Comedian
  • Send private message