30
TheoLog (Subject) / Komplexität (Lesson)
Advertisement
- Was bezeichnet man als Komplexität? Wovon hängt diese ab? Den Aufwand zur Berechnung einer Funktion, also quasi wie schwierig das Problem ist. Der Aufwand hängt von der Länge der Eingabe ab.
- Wie kann man Rechenzeit und Speicheraufwand auf eine Turing Maschine übertragen? Rechenzeit, wäre die Anzahl der Übergänge bis die TM anhält Speicheraufwand wäre die Anzahl genutzter Felder
- Welche Komplexitätsklassen gibt es? DTIME NTIME DSPACE NSPACE P NP EXPTIME P-Vollständig
- Welche Beziehungen gelten für Komplexitätsklassen? P ⊆ NP ⊆ PSPACE (bzw. NSPACE) ⊆ EXPTIME DTIME ⊆ DSPACE ⊆ NSPACE PSPACE = NSPACE
- Wann ist ein Problem in NP-vollständig? Das Problem liegt in NP und ist NP-hart, also liegt auch nur in NP. Diese Probleme sind alle nicht effizient lösbar.
- Sind alle Probleme in NP schwer? Nein, da P ebenfalls Teilmenge von NP ist, und P die effizient lösbaren Probleme sind.
- Welche Probleme sind NP Vollständig? SAT 3-SAT Clique 3-Färbbarkeit
- Warum liegt SAT in NP? Da es eine NTM gibt, welche die Elemente von SAT akzeptiert 1) Teste, ob die Eingabe ein Boolescher Ausdruck ist (entspricht dem Wortproblem für kontextfreie Grammatiken, polynomial entscheidbar). 2) Durchlaufe den Ausdruck und ersetze nichtdeterministisch jede Variable xi durch 0 oder 1(polynomialer Aufwand). 3) Werte den Ausdruck aus und akzeptiere, falls das Ergebnis 1 ist (geht polynomial)
- Was besagt der Satz von Cook? Ist ein Problem L0 NP-vollständig in P, so gilt P = NP (Gibt es nicht!) SAT ist NP vollständig
- Wie weisst man NP-Vollständigkeit nach? Problem ist in NP Man „rät“ eine Lösung und zeigt, dass man in Polynomialzeit verifizieren kann, ob die Lösung wirklich zutrifft. Im Raten der (korrekten) Lösung findet sich der Nichtdeterminismus wieder. Problem ist NP-hart Man nimmt für gewöhnlich ein ähnliches Problem, für das die NP-Vollständigkeit schon bekannt ist, und reduziert es auf dasjenige Problem, für das die Eigenschaft der NP-Schwere gezeigt werden soll. Aus der Transitivität von Polynomialzeitreduktionen folgt dann, dass alle anderen Probleme aus NP ebenfalls auf das betrachtete Problem reduzierbar sind.
- Advertisement
- Was ist 3SAT? Warum ist es NP Vollständig? Ein 3SAT-Problem ist eine endliche Konjunktion von 3-Klauseln. Es ist NP vollständig durch polynomielle Reduktion auf das SAT Problem. 3SAT ∈ NP folgt unmittelbar aus SAT∈NP, da jedes 3SAT-Problem ein Boolescher Ausdruck ist
- Was ist das Clique Problem? Wieso ist sie in NP? Hat ein Graph g eine Clique der Größe k? Dabei bezeichnet eine Clique Knoten, welche alle gegenseitig miteinander verbinden sind. Man rate eine Teilmenge der Größe k und testet dann ob sie eine k-Clique ist. Dies ist polynomiell lösbar und somit in NP.
- Was ist 3-Färbbarkeit? Wie lautet der NP Algorithmus? Kann man einen Graphen g mit drei Farben färben, ohne dass Nachbarn die gleiche Farbe haben? Dabei rät man eine von drei Farben für jeden Knoten und prüuft danach, ob die beiden Enden der Kante verschiedene Farben haben. Ist dies für alle Knoten der Fall, akzeptiere den Graphen.
- Ist die Zweifärbbarkeit von Graphen in NP? Ja, aber auch in P.
- Wie lautet der Satz von Appel? Jeder planare Graph ist 4-färbbar.
- Wann ist ein Problem PSPACE-vollständig? Wenn es in PSPACE liegt und PSPACE hart ist, also mindestens so schwer zu lösen, wie jedes andere Problem in PSPACE.
- Was besagt der Satz von Savitch? PSpace = NPSpace
- Warum ist PSPACE unter Komplement abgeschlossen? Da wenn L Teil von PSPACE ist auch /L in PSPACE enthalten sein muss.
- Was ist das Universalitätsproblem? Gegeben ist eine NTM . L(A) = Σ*? Es ist PSPACE vollständig.
- Sind alle NP-harten Probleme NP vollständig? Nein, beispielsweise ein modifiziertes SAT Problem, welches sich auf das Halteproblem reduzieren lässt. Dieses wäre NP hart, aber nicht entscheidbar, also nicht in NP. Diese Modifikation wäre zB. eine Turing Maschine, welche SAT entscheidet und bei positiver Antwort anhält und sonst nicht terminiert. -> Halteproblem
- Wofür dient polynomielle Reduktion? Um nachzuweisen, dass ein Problem NP-hart ist. Dies erfolgt durch Reduktion eines bekannten NP-harten Problems auf ein neues. Somit gilt L1 NP - hart und L2 NP-hart.
- Gibt es ein NP-hartes Problem, das in PSPACE liegt ? Ja, QBFSAT
- Gibt es ein NP-hartes Problem in P? Nein. Gäbe es ein NP-hartes Problem in P, so ließe sich jedes NP-Problem in polynomieller Zeit auf dieses reduzieren und läge damit selbst in P;also würde P = NP folgen
- Konstruktion von TM für Konkatenation und Komplement ! Komplement Falls A die Eingabe w akzeptiert, dann lehne die Eingabe ab. Ansonsten akzeptiere danach die Eingabe. Konkatenation Bei Eingabe w führt die TM folgende Schritte aus: (a) Rate eine Zerlegung w=w1w2. (b) Falls A1 die Eingabe w1 ablehnt, dann lehne die Eingabe ab (c) Falls A2 die Eingabe w2 ablehnt, dann lehne die Eingabe ab (d) Akzeptiere die Eingabe.
- Turingmaschine für Durchschnitt und Vereinigung! Durchschnitt (a) Falls A1 die Eingabe w ablehnt, dann lehne die Eingabe ab (b) Falls A2 die Eingabe w ablehnt, dann lehne die Eingabe ab (c) Akzeptiere die Eingabe Vereinigung (a) Falls A1 die Eingabe w akzeptiert, dann akzeptiere die Eingabe. (b) Falls A2 die Eingabe w akzeptiert, dann akzeptiere die Eingabe. (c) Lehne die Eingabe ab.
- Was ist PSPACE? PSPACE ist die Klasse der Entscheidungsprobleme, die von deterministischen Turingmaschinen mit polynomiellem Platz entschieden werden können
- Was ist QSAT? Erfüllbarkeitsproblem für quantifizierte boolesche Formeln Dieses Entscheidungsproblem untersucht, ob eine aussagenlogische Formel, die mit Quantoren versehen ist, erfüllbar oder wahr ist.
- Was ist die chromatische Zahl? Sie gibt an , wie n-färbbar der Graph maximal ist.
- Wann ist ein Graph bipartit? Wenn er keinen Kreis ungerader Länge als Teilgraph besitzt.
- Was ist das Problem der Mengenüberdeckung? Wie lautet der NP Algorithmus? Man hat gegeben eine Menge M und k Teilmengen A..Z Kann man k von den Teilmengen wählen, die M überdecken? (Ist ein Element in k Teilmengen enthalten) Wähle irgendwelche Teilmengen von M aus (k-Stück) Prüfe, ob jedes Element M in einer dieser Teilmengen liegt Falls ja, akzeptiere, falls nein, verwerfe