Komplexitätstheorie
144 flashcards · Computer Science · by Bennet Preimess
Was ist die O\mathcal{O}O -Notation?
Dient zur Einordnung der Laufzeit von Algorithmen. f∈o(g)f \in o(g)f∈o(g) (gesprochen: klein Oh) f wächst asymptotisch langsamer als g f∈ω(g)f \in \omega(g)f∈ω(g) (gesprochen: klein Omega) f wächst asymptotisch schneller als g f∈O(g)f \in \mathcal{O}(g)f∈O(g) (gesprochen: groß Oh) f wächst nicht wesentlich schneller als g f∈Θ(g)f \in \Theta(g)f∈Θ(g) (gesprochen: groß Theta) f und g wachsen gleich schnell f∈Ω(g)f \in \Omega(g)f∈Ω(g) (gesprochen: groß Omega) f wächst nicht wesentlich langsamer al…
Was ist das traveling salesperson problem (TSP)?
Problem, eine kürzeste Rundreise, die n vorgegebene Orte erreicht und zum Startpunkt zurück führt, zu berechnen.
Welche Unterscheidungen für das traveling salesperson problem (TSP) gibt es?
TSPsymTSP^{sym}TSPsym die Distanzen sind symmetrisch TSPΔTSP^\DeltaTSPΔ die Distanzen erfüllen die Dreiecksgleichung TSPd−EuklidTSP^{d - Euklid}TSPd−Euklid die Orte sind Punkte im euklidischen Raum Rd\mathbb{R}^dRd TSPNTSP^NTSPN die Distanzwerte stammen aus {1,...,N}\{1,...,N\}{1,...,N} DHC (gerichteter hamiltonscher Kreis, directed hamiltonian circuit) HC = DHCsymHC\ =\ DHC^{sym}HC = DHCsym
Was ist das knapsack problem (KP)?
Das Ziel besteht darin, den Gesamtnutzen der ausgewählten Objekte zu maximieren ohne dabei ein gefordertes Gesamtgewicht zu überschreiten. Spezialfall K∗K^*K∗ , bei dem Nutzen und Gewicht gleich ist.
Was ist das Problem PARTITION?
Ein Spezialfall von K∗K^*K∗ und BP. Aufteilung von Objekten in zwei Gruppen mit dem selben Maximalgewicht.
Was ist das Problem bin packing (BP)?
Problem bei dem Kisten der Größe b bereitstehen und wir n Objekte der Größen a1,...,ana_1,...,a_na1,...,an in möglichst wenige Kisten verpacken wollen.
Was ist das Problem vertex cover (VC)?
Es sollen alle Kanten eines Graphen mit möglichst wenigen Knoten überwacht werden.
Was ist das Problem CLIQUE?
Es soll eine möglichst große Clique (verbundene Knoten) berechnet werden.
Was ist das independent set problem (IS)?
Es soll eine möglichst große Anti-Clique (nicht verbundene Knoten) berechnet werden.
Was ist das Problem k-dimensional matching (k-DM)?
Bildung von Teams der Größe k 2-DM: Heiratsproblem
Was ist das Problem network flow (NF)?
Die Maximierung von Flüssen in Netzwerken.
Was ist das championship problem (CP)?
Klärung der Frage, ob eine Mannschaft zu einem Zeitpunkt theoretisch noch Meister werden kann.
Was ist das satisfiability problem (SAT)?
Prüfung, ob Spezifikation S und Realisierung R eines Chips dieselbe boolesche Funktion beschreiben
Welche Unterscheidungen für das satisfiability problem (SAT) gibt es?
SATCIRSAT_{CIR}SATCIR geht von der Eingabe als Schaltkreis (circuit) aus SAT = SATCF von einer konjunktiven Form (CF) SATDF von einer disjunktiven Form (DF) k-SAT alle Klauseln enthalten genau k Literale
Was ist die erweiterte Churchsche These?
Für je zwei Rechnermodelle R1 und R2 gibt es ein Polynom p, so dass t Rechenschritte auf R1 durch p(t) Rechenschritte auf R2 simuliert werden können.
Was ist ein deterministischer Algorithmus?
Ein Algorithmus heißt deterministisch (determiniert, deterministic), wenn zu jedem Zeitpunkt der nächste Rechenschritt deutig festgelegt ist.
Was sind Registermaschinen?
Registermaschinen haben den freien Zugriff (random access) auf ihren Speicher bei Eingabe i kann der Inhalt der i-ten Speicherzelle, früher auch Register genannt, gelesen werden.
Was sind Turingmaschinen?
Turingmaschinen haben die Eigenschaft, dass an einem Rechenschritt nur das Gedächtnis, die Leseposition und die betrachtete Speicherzelle beteiligt sind. Es kann danach nur eine benachbarte Speicherzelle aufgesucht werden.
Wann beträgt ein Problem eine algorithmische Komplexität von f(n)f(n)f(n) ?
Wenn das Problem durch einen Algorithmus A mit maximaler Rechenzeit O(f(n))O(f(n))O(f(n)) gelöst werden kann und jeder Algorithmus für das Problem eine maximale Rechenzeit von O(f(n))O(f(n))O(f(n)) hat.
Mit EP bezeichnen wir die Klasse der algorithmischen Probleme, für die es einen randomisierten Algorithmus mit polynomieller maximaler durchschnittlicher Rechenzeit gibt.
Die zugehörigen Algorithmen heißen Las- Vegas-Algorithmen. expected kolonial time
Mit ZPP(e(n)) bezeichnen wir die Klasse der algorithmischen Probleme, für die es einen randomisierten Algorithmus mit polynomieller maximaler Rechenzeit gibt, der für jede Eingabe der Länge nnn eine durch ϵ(n)<1\epsilon(n) < 1ϵ(n)<1 beschränkte Versagenswahrscheinlichkeit (failure probability) hat. Der Algorithmus liefert entweder ein korrektes Ergebnis oder versagt, indem er das Ergebnis "?" liefert.
Ein derartiger Algorithmus heißt Monte-Carlo-Algorithmus. zero-error probabilistic polynomial time
Mit BPP(e(n)) bezeichnen wir die Klasse der algorithmischen Probleme, für die es einen randomisierten Algorithmus mit polynomieller maximaler Rechenzeit gibt, der für jede Eingabe der Länge nn eine durch \epsilon(n) < 1/2ϵ(n)<1/2 beschränkte Fehlerwahrscheinlichkeit (Irrtumswahrscheinlichkeit, error probability) hat.
Dieser Fehlertyp wird als zweiseitiger Fehler (two-sided error) bezeichnet bounded-error probabilistic polynomialtime
Mit RP(e(n)) bezeichnen wir die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus mit polynomieller maximaler Rechenzeit gibt, der jede nicht zu akzeptierende Eingabe ablehnt und für jede zu akzeptierende Eingabe der Länge nn eine durch \epsilon(n) < 1ϵ(n)<1 beschränkte Fehlerwahrscheinlichkeit hat.
Dieser Fehlertyp wird als einseitiger Fehler (one-sided error) bezeichnet random polynomial time
Was ist die Markoffsche Ungleichung?
Mit der Markoffsche Ungleichung (statt Markov findet man auch Markow oder Markoff) kann abgeschätzt werden, wie wahrscheinlich bzw. unwahrscheinlich es ist, dass eine Zufallsvariable stark nach oben (um ein Vielfaches) von ihrem Erwartungswert abweicht
Wie lautet der Beweis von Theorem 3.3.1. EP=ZPP(1/2)EP = ZPP(1/2)EP=ZPP(1/2)
EP⊆ZPP(1/2)EP \subseteq ZPP(1/2)EP⊆ZPP(1/2) : Klassifizierung EP: randomisierter Algorithmus, der das Problem korrekt löst. Wahrscheinlichkeit für eine 2∗p(n)2 * p(n)2∗p(n) beschränkte Rechenzeit beträgt 1/21/21/2 (markoffsche Ungleichheit) => stoppen des Algorithmus' nach 2∗p(n)2*p(n)2∗p(n) Interpretation als Erfolg, wenn Alg. fertig, sonst Versagen ("?") ZP(1/2)⊆EPZP(1/2) \subseteq EPZP(1/2)⊆EP : Klassifizierung ZP: randomisierter Algorithmus, maximale Rechenzeit (beschränkt durch Polynom p(n…
Was wird auch probably amplification genannt?
Die Möglichkeit, die Versagenswahrscheinlichkeit bei ZPP Algorithmen durch Wiederholung zu senken. Theorem 3.3.2. Es seien p(n) und q(n) Polynome, dann ist ZPP(1−1/p(n))=ZPP(2q(n))ZPP(1 - 1/p(n)) = ZPP(2^{q(n)})ZPP(1−1/p(n))=ZPP(2q(n)) .
Ein algorithmisches Problem gehört zur Komplexitätsklasse P der polynomielllösbaren Probleme, wenn es durch einen Algorithmus mit polynomieller maximaler Rechenzeit gelöst werden kann.
Ein Entscheidungsproblem LLL gehört zur Komplexitätsklasse NP, wenn es einen nichtdeterministischenA lgorithmus mit polynomieller maximaler Rechenzeit gibt, der jedes x \in Lx∈L auf mindestens einem erlaubten Rechenweg akzeptiert und jedes x \notin Lx∈/L auf allen erlaubten Rechenwegen ablehnt.
nondeterministic polynomial time
Was ist ein nichtdeterministischer Algorithmus?
Ein nichtdeterministischer Algorithmus (nondeterministic algorithm) kann stets zwischen zwei Aktionen wählen, wobei es keine Vorschrift gibt, wie diese Aktion ausgewählt wird.
Welche Komplexitätsklassen sind gegen Komplementbildung ausgeschlossen und was bedeutet das?
P, ZPP, ZPP*, BPP und PP sind gegen Komplementbildung abgeschlossen, also gilt P = co-P, ZPP co-ZPP, ZPP* = co-ZPP*, BPP = co-BPP und PP = co-PP.
Wie stehen die Komplexitätsklassen P, ZPP, BPP, RP und PP zueinander?
Die Beziehungen P ⊆\subseteq⊆ ZPP, ZPP ⊆\subseteq⊆ ZPP* und BPP ⊆\subseteq⊆ PP folgen direkt aus den Definitionen. ZPP ⊆\subseteq⊆ RP und ZPP* ⊆\subseteq⊆ RP*, da die Antwort "?" für ein Versagen durch ein Ablehnen mit möglichem Fehler ersetzt werden kann. Analog ist co-ZPP ⊆\subseteq⊆ co-RP und, da ZPP = co-ZPP ist, auch ZPP ⊆\subseteq⊆ co-RP. Auf gleiche Weise folgt ZPP* ⊆\subseteq⊆ co-RP*. Durch probably amplification folgende Beobachtungen: ZPP = ZPP(1/2) = ZPP(1/3) ⊆\subseteq⊆ BPP(1/3) = B…
Warum ist ZPP = RP ∩\cap∩ co-RP und ZPP* = RP* ∩\cap∩ co-RP*?
Wenn L∈RP∩co−RPL \in RP \cap co-RPL∈RP∩co−RP ist, gibt es polynomielle RP-Algorithmen AAA und Aˉ\bar{A}Aˉ für LLL bzw. Lˉ\bar{L}Lˉ . Wir benutzen beide Algorithmen nacheinander, was natürlich zu einem polynomiellen randomisierten Algorithmus führt. Mögliche Ergebnisse: (1,0): Da A(x)=1A(x) = 1A(x)=1 ist, muss x∈Lx \in Lx∈L sein. (Falls x∉Lx \notin Lx∈/L , ist A(x)=0A(x) = 0A(x)=0 .) Also wird x akzeptiert. (0,1): Da Aˉ(x)=1\bar{A}(x) = 1Aˉ(x)=1 ist, muss x∉Lx \notin Lx∈/L sein. Also wird x abge…
Warum ist NP = RP*?
Die Definitionen von NP und RP* erwarten Algorithmen mit polynomieller maximaler Rechenzeit p(n) und zwei möglichen Aktionen in jeder Situation. Für x∉Lx \notin Lx∈/L NP muss auf allen Rechenwegen ablehnen (pro Rechenweg wahrscheinlichkeit von 2−p(n)2^{-p(n)}2−p(n) RP* lehnt x mit Wahrscheinlichkeit 1 ab Für x∈Lx \in Lx∈L NP muss auf mindestens einem Rechenweg akzeptieren RP* muss mit einer Wahrscheinlichkeit von kleiner 1 ablehnen Somit sind beide Algorithmen äquivalent.
Was bedeutet komplexitätstheoretisch ähnlich?
Zwei Probleme nennen wir komplexitätstheoretisch ähnlich, wenn sie in genau denselben der betrachteten Komplexitätsklassen enthalten sind.
Was bedeutet algorithmisch nicht schwieriger als?
Das Problem A ist algorithmisch nicht schwieriger als das Problem B, wenn es einen Algorithmus zur Lösung von Problem A gibt, der auf einen Algorithmus zur Lösung von Problem B zurückgreifen darf und folgende Eigenschaften hat: Die Rechenzeit ohne die Aufrufe des Algorithmus zur Lösung von B ist durch ein Polynom p(n)p(n)p(n) beschränkt. Die Anzahl der Aufrufe des Algorithmus zur Lösung von B ist durch ein Polynom q(n)q(n)q(n) beschränkt. Die Eingabelänge für jeden Aufruf des Algorithmus zur Lö…
Eigenschaften von Polynomen p1 von Grad d1 und p2 von Grad d2
Die Summe p1 + p2 ist ein Polynom, dessen Grad höchstens max{d1, d2} ist. Das Produkt p1 • p2 ist ein Polynom, dessen Grad d1 + d2 ist. Die Komposition (oder Verknüpfung) p1 ° p2 (oder p1(p2)) ist ein Polynom, dessen Grad d1 • d2 ist.
Was bedeutet ≤T\leq_T≤T ?
die Aussage "A ist algorithmisch nicht schwieriger als B" wird durch A ≤T\leq_T≤T B abgekürzt. Ausführlicher: A wurde auf B turingreduziert. Der Algorithmus für A, der sich aus der Turingreduktion auf B ergibt, wird oft Algorithmus mit Orakel (oracle) B genannt. Wir befragen ein Orakel, dass uns zuverlässig Antworten auf das Problem B liefert.
Wie lautet der Beweis von Theorem 4.3.1.: DHC=THC≤TTSP2,Δ,symDHC =_T HC \leq_T TSP^{2,\Delta, sym}DHC=THC≤TTSP2,Δ,sym ?
HC≤TDHCHC \leq_T DHCHC≤TDHC : Um DHC zum Lösen von HC zu nutzen wird ein neuer Graph G' erzeugt, der zu jeder Kante seine Gegenrichtungskante hinzufügt. Der Algorithmus für DHC wird dann auf dem neuen Graphen G' aufgerufen und das Ergebnis auf HC übertragen p(n,m)=O(n+m),q(n,m)=1p(n,m) = O(n + m), q(n, m) = 1p(n,m)=O(n+m),q(n,m)=1 DHC≤THCDHC \leq_T HCDHC≤THC : Knoten zwischen denen Verbindungen in beide Richtungen bestehen werden durch kleine Grahen ersetzt, damit die Verbindung immer nur in…
Wie lautet der Beweis von Theorem 4.3.2.: SAT≤T3−SATSAT \leq_T 3-SATSAT≤T3−SAT ?
Klauseln der SAT-Eingabe durch Klauselmengen mit Klauseln, die je drei Literale enthalten ersetzen, sodass die gegebene Klauselmenge genau dann erfüllbar ist, wenn dies die neue Klauselmenge ist. Klauseln mit höchstens drei Literalen werden durch Wiederholung von Literalen verlängert. Zu lange Literale werden aufgetrennt und durch neue Variablen verkettet, die die zugehörige Klausel erfüllt, wenn eine andere Klausel aus der "Kette" erfüllt ist Wenn wir die Eingabelänge lll durch die Anzahl der…
Wie lautet der Beweis für Theorem 4.3.3.: PARTITION≤TBPPARTITION \leq_T BPPARTITION≤TBP
PARTITION ist der Spezialfall von BP, in dem es zwei Kisten gibt und die Objekte den Raum in den Kisten voll ausfüllen. Wenn wir BP auf die Zahlen g1,...,gng_1,...,g_ng1,...,gn und zwei Kisten der Größe b:=⌊(g1+...+gn)/2⌋b := \lfloor(g_1 + ... + g_n)/2 \rfloorb:=⌊(g1+...+gn)/2⌋ anwenden, erhalten wir auch die richtige Antwort für PARTITION.
Wie lautet der Beweis für Theorem 4.3.4.: CLIQUE=TIS=TVCCLIQUE =_T IS =_T VCCLIQUE=TIS=TVC ?
CLIQUE=TISCLIQUE =_T ISCLIQUE=TIS : Wir konstruieren einen Graphen G' aus G, der genau die Kanten enthält, die G nicht enthält. G' enthält eine Anticlique, wenn G eine Clique enthält Hier ist p(n) = O(n2), da wir alle (n2)\binom{n}{2}(2n) möglichen Kanten betrachten, q(n) = 1 und r(n) = n. IS≤TVCIS \leq_T VCIS≤TVC : Eingabe für IS: Graph G(V,E) und Schranke k Überlegung, wenn es k unabhängige Knoten gibt müssen n - k Knoten alles überwachen Eingabe für VC: der Graph G und eine Schranke von n…
Wie lautet der Beweis für Theorem 4.4.1.: 2−DM≤TNF2-DM \leq_T NF2−DM≤TNF ?
Modelierung des Heiratsproblem als Graph Für ein Matching mit k Kanten muss jeder Fluss mit Wert k Fluss auf k Kanten, die von sss ausgehen, und k Kanten, die ttt erreichen, legen. Es werden k U-Knoten u1,...,uku_1,...,u_ku1,...,uk vom Fluss erreicht und k W-Knoten w1,...,wkw_1,...,w_kw1,...,wk müssen Fluss an t weitergeben Hier ist p(n,m)=O(n+m)p(n, m) = O(n + m)p(n,m)=O(n+m) , q(n,m)=1q(n, m) = 1q(n,m)=1 und die Eingabe für NF hat n + 2 Knoten und n + m Kanten, wenn das Matchingproblem n…
Wie lautet der Beweis für Theorem 4.4.2.: Für das Meisterschaftsproblem a-CP mit a-Aufteilungsregel gilt a−CP≤TNFa-CP \leq_T NFa−CP≤TNF ?
Ausgewählter Verein gewinnt alle Spiele und erhält A Punkte Entscheiden, ob die restlichen Vereine höchstens A Punkte bekommen können
Wie lautet der Beweis für Theorem 4.4.3.: 3−SAT≤TCLIQUE3-SAT \leq_T CLIQUE3−SAT≤TCLIQUE ?
Jede Klausel wird durch 3 nicht verbundene Knoten repräsentiert Verbindung von zwei Knoten aus verschiedenen Gruppen, wenn dessen Literale gemeinsam erfüllbar sind Da die Erfüllbarkeit bei 3-SAT die gemeinsame Erfüllbarkeit aller m Klauseln bedeutet, interessieren wir uns für Cliquen der Größe m. Der entstandene Graph hat 3m Knoten und O(m2 ) Kanten. Außerdem ist p(n, m) = O(m2 ) und q(n, m) = 1.
Wie lautet der Beweis für Theorem 4.4.4.: 3−SAT≤TDHC3-SAT \leq_T DHC3−SAT≤TDHC ?
Graph aus 3-Sat besteht aus Variablenkomponenten und Klauselkomponenten Klauselkomponenten bestehen nur aus einem Knoten Variablenkomponenten bestehen aus Rahmen pro Variable xix_ixi :Knoten für Start und Entscheidung, ob xix_ixi oder xiˉ\bar{x_i}xiˉ Für jedes Vorkommen von xix_ixi bzw. xiˉ\bar{x_i}xiˉ zwei Knoten p(n, m) = O(n+m) und q(n, m) = 1
Wie lautet die Definition für polynomiell reduzierbar?
Das Entscheidungsproblem A ist auf das Entscheidungsproblem B polynomiell reduzierbar (polynomial-time reducible, many-one reducible), Notation A≤pBA \leq_p BA≤pB , wenn es eine in polynomieller Zeit berechenbare Funktion f gibt, die Eingaben für A auf Eingaben für B so abbildet, dass für die zugehörigen Sprachen LAL_ALA und LBL_BLB gilt: Die Entscheidung für B darf nicht bearbeitet werden.
Wie lässt sich ein Algorithmus A in Bezug auf eine Komplexitätsklasse CCC klassifiziert?
A heißt CCC -schwierig ( CCC -hart, CCC -hard) bezüglich " ≤p\leq_p≤p ", wenn C≤pAC \leq_p AC≤pA für jedes C∈CC \in CC∈C A heißt CCC -einfach ( CCC -leicht, CCC -simple) bezüglich " ≤p\leq_p≤p ", wenn A≤pCA \leq_p CA≤pC für ein C∈CC \in CC∈C A heißt CCC -äquivalent ( CCC -equivalent) bezüglich " ≤p\leq_p≤p ", wenn A sowohl CCC -schwierig bezüglich " ≤p\leq_p≤p " als auch CCC -einfach bezüglich " ≤p\leq_p≤p " ist. A heißt CCC -vollständig ( CCC -complete) bezüglich " ≤p\leq_p≤p ", wenn A…
Was ist die Aussage des NP≠PNP \neq PNP=P - Problems?
Tausende von wichtigen Problemen sind NP-vollständig oder NP-äquivalent. Entweder sind all diese Probleme in polynomieller Zeit lösbar und es ist NP=PNP = PNP=P oder all diese Probleme sind nicht in polynomieller Zeit lösbar und es ist NP≠PNP \neq PNP=P .
Wie lautet die NP≠PNP \neq PNP=P Hypothese?
Entscheidungsprobleme sind genau dann in NP enthalten, wenn sich die zugehörige Sprache LLL durch einen polynomieIl längenbeschränkten Existenzquantor ( ∃z∈{0,1}p(∣x∣)\exists z \in \{0, 1\}^{p(|x|)}∃z∈{0,1}p(∣x∣) ) und ein polynomieIl entscheidbares Prädikat ( (x,y)∈L′(x,y) \in L'(x,y)∈L′ ) darstellen lässt. Beispiel TSP: Die Entscheidungsvarianten der Optimierungsprobleme sind durch Existenzquantoren (es gibt eine Rundreise) mit polynomiellen Prädikaten (die Kosten der Rundreise sind durch D b…
Wie lautet der Beweis von Theorem 5.4.3. (Theorem von Cook) SAT ist NP-vollständig. Anders ausgedrückt: Es ist NP = P genau dann, wenn SAT ∈\in∈ P ist.
Eine Turingmaschine bietet folgende Komponenten: die Zustände die Zufallsbits den Inhalt der Speicherzellen Die Komponenten werden durch boolesche Variablen repräsentiert Es gibt vier Bedingungen, die als Konjunktionen von Klauseln codiert werden: Die Variablen für t = 0 korrespondieren zur Anfangskonfiguration der Rechnung. Die letzte Konfiguration ist akzeptierend. Die Variablen stellen Konfigurationen dar. Die t-te Konfiguration ist gemäß den Vorschriften von M Nachfolgekonfiguration der (t…
Was ist das Problem HP?
Ein hamiltonscher Pfad ist ein Weg, der jeden Knoten des Graphen genau einmal berührt. Das entsprechende Problem für ungerichtete Graphen heißt HP.
Wie lautet der Beweis von Theorem 6.2.1. DHP und HP sind NP-vollständig?
Der Beweis von Theorem 4.4.4 hat gezeigt, dass 3−SAT≤pDHC3-SAT \leq_p DHC3−SAT≤pDHC ist. Aus der dort beschriebenen polynomiellen Reduktion wird eine polynomielle Reduktion, die 3−SAT≤pDHP3-SAT \leq_p DHP3−SAT≤pDHP zeigt, wenn wir die beiden v1,1v_{1,1}v1,1 erreichenden Kanten weglassen. Analog zum Beweis von DHC≤pHCDHC \leq_p HCDHC≤pHC (Theorem 4.3.1) lässt sich DHP≤pHPDHP \leq_p HPDHP≤pHP zeigen.
Was ist das Problem BMST?
Minimale Spannbäume haben die Tendenz, "sternförmig" zu sein, insbesondere haben oft einige Knoten einen hohen Grad. Wenn dies in den Anwendungen nicht erwünscht ist, kann man als Nebenbedingung eine Gradschranke kkk für die Knoten hinzufügen und kommt zum Problem der Berechnung gradbeschränkter minimaler Spannbäume (BMST, bounded-degree minimum-cost spanning tree).
Wie lautet der Beweis von Theorem 6.2.2. BMST ist NP-vollständig?
Natürlich ist die Entscheidungsvariante von BMST in NP enthalten. In der polynomiellen Reduktion HC≤pTSP2,Δ,symHC \leq_p TSP^{2, \Delta, sym}HC≤pTSP2,Δ,sym haben wir di,j=1d_{i,j} = 1di,j=1 gesetzt, falls {i,j}∈E\{i, j\} \in E{i,j}∈E ist, und ansonsten di,j=2d_{i,j} = 2di,j=2 . Ebenso gehen wir bei der polynomiellen Reduktion HP≤pBMSTHP \leq_p BMSTHP≤pBMST vor, wobei wir zusätzlich die Gradschranke kkk auf 222 setzen. Ein Spannbaum mit Maximalgrad 2 muss aber ein hamiltonscher Pfad sein. Al…
Was ist das Problem SSS?
Die Frage, ob es eine Indexmenge I⊆{1,...,n}I \subseteq \{1,...,n\}I⊆{1,...,n} gibt, dessen Summe aller gi,i∈Igi, i \in Igi,i∈I , genau G ist. In dieser Form wird das Problem Teilsummenproblem (subset sum problem, SSS) genannt.
Wie lautet der Beweis von Theorem 6.3.1. SSS ist NP-vollständig?
Es wird 3−SAT≤pSSS3-SAT \leq_p SSS3−SAT≤pSSS gezeigt Dazu werden pro Klausel 2 Zahlen (d und e) und pro Variable 2 Zahlen (a uns b) erzeugt Die Zahlen haben die Länge der Summe aus Klausel- und Variablenanzahl Die Wahl von ai=1a_i = 1ai=1 bedeutet xix_ixi , die Wahl von bi=1b_i = 1bi=1 bedeutet xˉ\bar{x}xˉ Wenn wir nun eine Variablenbelegung wählen und die zugehörige Auswahl zwischen aia_iai und bib_ibi treffen, erhalten wir an der Position für cjc_jcj die Summe sjs_jsj , wenn die Klaus…
Wie lautet der Beweis von Korollar 6.3.2. KP und PARTITION sind NP-vollständig?
Es wird SSS≤pPARTITIONSSS \leq_p PARTITIONSSS≤pPARTITION gezeigt Den Eingabewerten von SSS (s1,...,sn,S)(s_1,...,s_n,S)(s1,...,sn,S) SSS ist der geforderte Summenwert ...werden die erzwingenden Komponenten hinzugefügt 2S∗+S2S^*+S2S∗+S S∗+SS^*+SS∗+S Wenn es eine Teilmenge gibt, die den geforderten Summenwert bildet, erreicht man mittels eines der erzwingenden Komponenten S∗S^*S∗ , somit lässt sich das Problem mittels PARTITIONPARTITIONPARTITION lösen.
Was ist das Problem SWI?
SWI (sequencing with intervals) ist ein Aufteilungsproblem. Gegeben ist eine endliche Menge A von Aufgaben, jede Aufgabe a hat eine Bearbeitungsdauer l(a), einen frühesten Zeitpunkt r(a) (release time) für den Start ihrer Bearbeitung, einen spätesten Zeitpunkt d(a) (deadline) für die Beendigung der Arbeit und die Bearbeitung einer Aufgabe darf nicht unterbrochen werden. Das Problem SWI besteht darin zu entscheiden, ob die Aufgaben auf einem Prozessor so bearbeitet werden können, dass alle Neben…
Wie lautet der Beweis von Theorem 6.4.2. SWI ist NP-vollständig?
Es wird PARTITION≤pSWIPARTITION \leq_p SWIPARTITION≤pSWI und SWI≤pPARTITIONSWI \leq_p PARTITIONSWI≤pPARTITION gezeigt Dafür werden aus den nnn Eingaben n+1n+1n+1 Aufgaben erzeugt Die erzwingende Komponente ist eine Aufgabe, dessen Länge 1 ist, release ist n/2n/2n/2 und deadline ist n/2+1n/2+1n/2+1
Was ist das Problem SI?
Das Teilgraphenisomorphieproblem (subgraph isomorphism, SI) beschäftigt sich mit der Frage, ob es einen Teilgraphen G1′=(V1′,E1′)G'_1=(V'_1, E'_1)G1′=(V1′,E1′) von G1G_1G1 gibt, der isomorph zu G2G_2G2 ist. Ein Teilgraph G1′G'_1G1′ von G1G_1G1 wird durch die Wahl der Knotenmenge V1′⊆V1V'_1 \subseteq V_1V1′⊆V1 bestimmt, die Menge E1′E'_1E1′ enthält dann alle Kanten aus E1E_1E1 , die zwischen Knoten aus V1′V'_1V1′ verlaufen.
Wie lautet der Beweis von Theorem 6.5.2. CC und GC sind NP-vollständig?
GC ist Knoten!ärbungsproblem (graph colorability, GC)Es wird 3−SAT≤pGC3-SAT \leq_p GC3−SAT≤pGC gezeigt Eingabe für 3−SAT3-SAT3−SAT : Klauseln c1,...,cmc_1,...,c_mc1,...,cm auf x1,...,xnx_1,...,x_nx1,...,xn Anzahl der erlaubten Farben wird auf 3 gesetzt Erzwingende Komponente ist ein Dreieck auf v1v_1v1 , v2v_2v2 , v3v_3v3 Diese Knoten müssen verschieden gefärbt werden, es ergibt sich f(v1)=1f(v_1) = 1f(v1)=1 , f(v2)=2f(v_2)=2f(v2)=2 und f(v3)=3f(v_3)=3f(v3)=3 Die Literale x1,x1ˉ,...,…
Wie lautet der Beweis von Theorem 6.6.1. 3-DM ist NP-vollständig?
Es wird 3−SAT≤p3−DM3-SAT \leq_p 3-DM3−SAT≤p3−DM gezeigt Sei mmm die Anzahl der Klauseln c1,...,cmc_1,...,c_mc1,...,cm mit je drei Literalen über x1,...,xnx_1,...,x_nx1,...,xn Eingabe für 3−DM3-DM3−DM besteht aus 3 Expertengruppen, die je 6m6m6m Personen beinhalten 1. Expretengruppe unterteilt in nnn Untergruppen (für jede Variable eine) Zu der Untergruppe einer Variable gehören ( 2zi2z_i2zi ) doppelt so viele Personen, wie es Vorkommen der Variable xix_ixi und xiˉ\bar{x_i}xiˉ gibt Eine…
Was sind Probleme auf großen Zahlen?
Probleme, bei denen Zahlen, deren Größe nicht polynomiell in der Eingabelänge beschränkt ist, nicht sinnlos sind. Das Cliquenproblem ist beispielsweise durch k∈{2,...,n}k \in \{2,...,n\}k∈{2,...,n} beschränkt und somit kein Problem auf großen ZahlenProbleme auf großen Zahlen sind Rundreiseprobleme, Rucksackprobleme, Aufteilungsprobleme, Flussprobleme, Meisterschaftsprobleme und zahlentheoretische Probleme von der Art, dass Zahlen, deren Werte nicht polynomiell in der Eingabelänge beschränkt sin…
Wie lautet die Definition von stark NP-Vollständig?
Ein Entscheidungsproblem A auf großen Zahlen heißt stark NP-vollständig (NP-complete in the strong sense), wenn es für ein Polynom p(n)p(n)p(n) und Eingaben, bei denen alle Zahlen aus N\mathbb{N}N und bei Eingabelänge nnn durch p(n)p(n)p(n) beschränkt sind, NP-vollständig ist.
Wie lautet der Beweis von Theorem 7.2.2. Das Rundreiseproblem TSP und das Meisterschajtsproblem CP mit (0,1, a)-Aufteilungsregel sind stark NP-vollständig?
Wir wissen bereits, dass TSP selbst dann NP-vollständig ist, wenn die Distanzen nur Werte aus {1,2}\{1,2\}{1,2} annehmen dürfen. Die größte vorkommende Zahl ist dann nnn als Name des letzten Ortes. CP ist für die (0,1,3)-Aufteilungsregel NP-vollständig und damit sind die Zahlen in der Eingabe durch die Anzahl der beteiligten Vereine und ausstehenden Spiele beschränkt.
Wie lautet der Beweis von Theorem 7.2.3. Falls NP ≠\neq= P ist, ist das Rucksackproblem KP nicht stark NP-vollständig.
Wir geben einen Algorithmus für KP an, der für polynomiell beschränkte Gewichtswerte polynomielle Rechenzeit hat. Der Algorithmus nutzt die Methode der dynamischen Programmierung KP(k, g) bezeichnen wir das Teilproblem, bei dem nur die ersten k Objekte betrachtet werden und die Gewichtsgrenze g beträgt. N(k, g) gibt den größten zu erreichenden Nutzen von KP(k, g) an D(k, g) gibt die Entscheidung an, ob bei einer optimalen Bepackung g eingepackt wird oder nicht Algorithmus füllt zeilenweise eine…
Wann ist ein Algorithmus pseudopolynomiell?
Wir nennen einen Algorithmus für ein Problem auf großen Zahlen pseudopolynomiell (pseudo-polynomial), wenn er für jedes Polynom p(n)p(n)p(n) und Eingaben, bei denen alle Zahlen natürliche durch p(n)p(n)p(n) in ihrer Größe beschränkte Zahlen sind, eine polynomielle Rechenzeit hat. Falls NP ≠\neq= P ist, gibt es für stark NP-vollständige Probleme nicht einmal pseudopolynomielle Algorithmen.
Wie lautet der Beweis von Theorem 7.2.5. BP und SWI sind stark NP-vollständig?
Die Aussage für BP ist offensichtlich, da 3-PARTITION ein Spezialfall von BP ist. Zum Beweis der Aussage für SWI geben wir eine polynomielle Reduktion von 3-PARTITION auf SWI an Eingabe für 3-PARTITION: n=3kn = 3kn=3k , bbb und a1,...,ana_1,..., a_na1,...,an mit b/4<ai<b/2b/4 < a_i < b/2b/4<ai<b/2 und die Summe aller aia_iai beträgt k∗bk * bk∗b Mapping auf SWI Die Objekte werden durch Aufgaben A1,...,AnA_1,...,A_nA1,...,An repräsentiert, ergänzt um k−1k-1k−1 erzwingende Komponenten E1,...…
Wie ist die Approximationsgüte für Optimierungsprobleme definiert?
Für Optimierungsprobleme ist die Approximationsgüte (approximation ratio) r(x,s)r(x, s)r(x,s) einer für eine Eingabe xxx zulässigen Lösung s definiert durch vopt(x)/v(x,s)v_{opt}(x) / v(x, s)vopt(x)/v(x,s) bei Maximierungsproblemen und v(x,s)/vopt(x)v(x,s) / v_{opt}(x)v(x,s)/vopt(x) bei Minimierungsproblemen
Was ist ein Approximationsproblem?
Ein Approximationsproblem (approximation problem) ist ein Optimierungsproblem, bei dem nicht notwendigerweise die Berechnung einer optimalen Lösung verlangt wird, sondern es ausreicht, eine vorgegebene (asymptotische) maximale Approximationsgüte in polynomieller Zeit zu erreichen.
Wie lautet die Definition für die Komplexitätsklassen APX(r(n)) und APX?
Es sein r:N→[1,∞)r: \mathbb{N} \to [1, \infty)r:N→[1,∞) mit r(n+a)≥r(n)r(n+a) \geq r(n)r(n+a)≥r(n) gegeben. Die Komplexitätsklasse APX(r(n)) enthält alle Approximationsprobleme, die mit maximaler Approximationsgüte rA(n)≤r(n)r_A(n) \leq r_(n)rA(n)≤r(n) durch einen polynomiellen Algorithmus A gelöst werden können. APX ist die Vereinigung aller APX(c) mit c ≥\geq≥ 1
Wie lautet die Definition für ein polynomielles Approximationsschema (polynomialtime approximation scheme, PTAS)?
Ein polynomielles Approximationsschema (polynomialtime approximation scheme, PTAS) für ein Approximationsproblem ist ein Algorithmus A, der auf Eingaben (x, ϵ\epsilonϵ ) arbeitet, wobei x eine Eingabe für das Problem und 0"> ϵ>0\epsilon > 0ϵ>0 eine rationale Zahl ist, und für fest gewähltes ϵ\epsilonϵ in polynomieller Zeit bezogen auf die Länge von x eine Lösung mit maximaler Approximationsgüte 1+ϵ1 + \epsilon1+ϵ berechnet. Die Komplexitätsklasse PTAS enthält alle Optimierungsprobleme, für die…
Wie lautet die Definition für ein echt polynomielles Approximationsschema (fully polynomial-time approximation scheme, FPTAS)?
Ein echt polynomielles Approximationsschema (fully polynomial-time approximation scheme, FPTAS) ist ein PTAS, bei dem die Rechenzeit durch ein Polynom bezüglich der Länge von x und des Wertes von 1/ϵ1/\epsilon1/ϵ beschränkt ist. Die Komplexitätsklasse FPTAS enthält alle Optimierungsprobleme, für die es ein echt polynomielles Approximationsschema gibt.
Wie lautet ein Approximationsalgorithmus vom Knotentüberdeckungsproblem MIN-VC?
In linearer Zeit durchlaufen wir die Liste der Kanten und wählen eine Kante aus, wenn beide Endknoten noch frei sind. Zu Beginn sind alle Knoten frei und bei Wahl einer Kante wechseln beide Endknoten ihren Status von "frei" in "besetzt". Die Ausgabe besteht in der Menge der besetzten Knoten. Bei Wahl von k Kanten enthalt die Knotentüberdeckung 2k Knoten. Die k Kanten haben keinen Knoten gemeinsam. Daher sind k Knoten nötig, um allein die gewählten Kanten zu überdecken. Also haben wir eine Appro…
Wie lautet ein Approximationsalgorithmus für MAX-3-Sat?
Sei Xi eine Zufallsvariable, die die Erfüllung der Klausel ci repräsentiert. Die Wahrscheinlichkeit für das Erfüllen einer Klausel mit 3 Literalen beträgt 7/8. Somit ist die Wahrscheinlichkeit einer erfüllenden Belegung von m Klauseln bei m * 7/8 Die Wahrscheinlichkeit nimmt bei zunehmender "falscher" Belegung der Variablen ab. Sei b die die Variable, die den Wert der Variablen xi repräsentiert, dann gibt es ein bn ∈\in∈ {0,1}, sodass E(X∣xn=bn)≥(7/8)∗mE(X | x_n = b_n) \geq (7/8) * mE(X∣xn=bn…
Was ist ein (a, b)-Lückenproblem?
Ein (a, b)-Lückenproblem ist ein Optimierungsproblem bei dem der Wert zulässiger Lösungen mindestens a oder höchstens b > a ist. Beispiel anhand von HC≤pTSPHC \leq_p TSPHC≤pTSP : Distanzwerte für vorh. Verb. bleiben 1 Distanzwerte für andere Verb. von 2 auf 2n Daraus ergibt sich: TSP ist ein NP-schwieriges (n, 2n + n -1)-Lückenproblem.
Was sind Probleme auf kleinen Lösungswerten?
Ein Optimierungsproblem wird als Problem mit kleinen Lösungswerten bezeichnet, wenn die Werte aller Lösungen positiv, ganzzahlig und polynomiell in der Eingabelänge beschränkt sind.
Wie lautet der Beweis von Theorem 8.3.3. Falls NP ≠\neq= P ist, haben NP-schwierige Probleme mit kleinen Lösungswerten kein FPTAS?
Es sei p(n) eine polynomielle Schranke für die Lösungswerte Ein FPTAS für ε(n):=1/p(n)\varepsilon(n) := 1/p(n)ε(n):=1/p(n) ein polynomieller Approximationsalgorithmus, da Rechenzeit polynomiell in der Eingabelänge nnn und 1/ε(n)=p(n)1/\varepsilon(n) = p(n)1/ε(n)=p(n) beschränkt ist. Da NP ≠\neq= P & Problem NP-schwierig berechnet es nicht auf allen Wegen eine optimale Lösung Die maximale Approximationsgüte ist mindestens: 1 + \varepsilon(n)"> p(n)/(p(n)−1)=1+1/p(n)−1>1+ε(n)p(n)/(p(n)-1) = 1 +…
Was ist eine PTAS-Reduktion?
Eine PTAS-Reduktion eines Optimierungsproblems A auf ein Optimierungsproblem B, Notation A ≤PTAS\leq_{PTAS}≤PTAS B, besteht aus einem Tripel (f,g,α)(f, g, \alpha)(f,g,α) von Abbildungen mit folgenden Eigenschaften: fff bildet Eingaben xxx des Problems A auf Eingaben f(x)f(x)f(x) des Problems B ab und ist in polynomieller Zeit berechenbar, ggg bildet Tripel aus Eingaben xxx des Problems A, Lösungen y∈SB(f(x))y \in S_B(f(x))y∈SB(f(x)) und Zahlen ε∈Q+\varepsilon \in \mathbb{Q}^+ε∈Q+ auf Lösungen…
Wie lautet der Beweis von Lemma 8.4.2. Falls A ≤PTAS\leq_{PTAS}≤PTAS B und B ∈\in∈ PTAS gelten, ist A ∈\in∈ PTAS.
Eingabe für PTAS für A: xxx für A ε∈Q+\varepsilon \in \mathbb{Q}^+ε∈Q+ Berechnung in polyzeit von f(x)f(x)f(x) und a(ε)a(\varepsilon)a(ε) und Anwendung des PTAS für B mit ( f(x)f(x)f(x) , a(ε)a(\varepsilon)a(ε) ) erhalten von a(ε)a(\varepsilon)a(ε) -optimaler Lösung y∈SB(f(x))y \in S_B(f(x))y∈SB(f(x)) Dann berechnen wir in polynomieller Zeit g(x,y,ε)∈SA(x)g( x, y, \varepsilon) \in S_A(x)g(x,y,ε)∈SA(x) und geben das Resultat als Lösung für x aus. Die letzte Eigenschaft von PTAS-Reduktionen sic…
Wie lautet die Definition der Komplexitätsklasse NPO?
Ein Optimierungsproblem A gehört zur Komplexitätsklasse NPO (nondeterministic polynomial-time optimization problems), wenn es für eine Eingabe (x, s) in polynomieller Zeit möglich ist, zu überprüfen, ob s eine für x zulässige Lösung ist, und im positiven Fall v(x, s) zu berechnen. Die Klasse NPO eingeschränkt auf Maximierungsprobleme wird mit MAX-NPO und eingeschränkt auf Minimierungsprobleme mit MIN-NPO bezeichnet.
Worum handelt es sich bei dem Problem MAX-W-SAT?
Das Problem der Berechnung einer erfüllenden Belegung mit maximalem Gewicht (maximum weighted satisfiability, MAX-W-SAT) erhält als Eingabe Klauseln und nicht negative ganzzahlige Gewichte für die beteiligten Variablen. Die Lösungsmenge besteht aus allen Belegungen der Variablen. Der Wert einer erfüllenden Belegung ist gleich dem Maximum von dem Gesamtgewicht der mit 1 belegten Variablen und 1. Der Wert jeder anderen Belegung beträgt 1.
Wie lautet die Definition von NPI?
NPI := NP - (P ∪\cup∪ NPC) (NP incomplete bzw. NP intermediate)
Welche Probleme galten als gute Kandidaten für NPI?
- das Problem lineare Optimierung (linear programming, LP), also die Frage, ob eine lineare Funktion auf einem durch lineare Ungleichungen beschränkten Raum einen Funktionswert annehmen kann, der mindestens so groß wie eine vorgegebene Schranke b ist, Schon vor längerer Zeit wurde nachgewiesen, dass LP ∈\in∈ P ist (siehe z. B.Aspvall und Stone (1980))- den Primzahltest PRIMES und Agrawal, Kayal und Saxena haben (2002) bewiesen, dass PRIMES ∈\in∈ P ist- das Graphenisomorphieproblem GI (siehe Kap…
Wie lautet der Beweis von Theorem 10.2.2. Falls L NP-vollständig und L ∈\in∈ co-NP ist, dann gilt NP = co-NP?
Es genügt aus aus den Voraussetzungen und L' ∈\in∈ NP zu folgern, dass L' ∈\in∈ co-NP ist. Dies ist Äquivalent zu L′ˉ\bar{L'}L′ˉ ∈\in∈ NP Wir beschr. eine polynomiell zeitbeschränkte Turingmaschiene, die w∈L′ˉw \in \bar{L'}w∈L′ˉ akzeptiert und w∉L′ˉw \notin \bar{L'}w∈/L′ˉ verwirft Da L ∈\in∈ NPC und L' ∈\in∈ NP, L′≤pLL' \leq_p LL′≤pL Es gibt eine Funktion f, die Eingaben w für L' auf Eingaben f(w) für L abbildet f Anwendung auf Eingaben für L′ˉ\bar{L'}L′ˉ , bildet dann auf Eingaben für Lˉ\bar{…
Wie lautet die Definition für P( C\mathcal{C}C )?
Die Komplexitätsklasse P(L) enthält für ein Entscheidungsproblem L alle Entscheidungsprobleme L' mit L' ≤T\leq_T≤T L, also alle L', die sich durch polynomielle Algorithmen mit Orakel L entscheiden lassen. Die Komplexitätsklasse P( C\mathcal{C}C ) ist für eine Klasse C\mathcal{C}C von Entscheidungsproblemen die Vereinigung aller P(L), L ∈\in∈ C\mathcal{C}C .
Wie lautet die Definition für NP( C\mathcal{C}C )
Die Komplexitätsklasse NP(L) enthält für ein Entscheidungsproblem L alle Entscheidungsprobleme L', die sich durch polynomiell zeitbeschränkte nichtdeterministische Algorithmen mit Orakel L entscheiden lassen. Die Komplexitätsklasse NP( C\mathcal{C}C ) ist für eine Klasse C\mathcal{C}C von Entscheidungsproblemen die Vereinigung aller NP(L), L ∈\in∈ C\mathcal{C}C .
Was ist die Sprache aller MC?
Die Sprache aller minimalen Schaltkreise über der Basis aller binären Bausteine (minimal circuits, MC) besteht aus allen Schaltkreisen mit einem Ausgabebaustein, so dass kein Schaltkreis mit weniger Bausteinen (manchmal auch Gatter genannt) dieselbe boolesche Funktion berechnet.
Wie lautet der Beweis von Theorem 10.3.3. MC ∈\in∈ co-NP(NP)?
Wir zeigen MCˉ\bar{MC}MCˉ ∈\in∈ NP(NP) Gg. Schaltkreis S der die Funktion f berechnet Erz. nichtdeterministisch in polynomieller Zeit ein Schaltkreis S' der die Funktion f' berechnet mit weniger Bausteinen Bilden von S'' mittels EXOR: S'' = S ⊕\oplus⊕ S' und f'' = f ⊕\oplus⊕ f' Als Orakel wählen wir SATCIR (NP-Vollständig) Das Orakel akzeptiert, wenn f''(a) = a, also f(a) ≠\neq= f'(a) Algorithmus akzeptiert S nicht (Erinnerung: wir prüfen das Komplement) Akzeptiert das Orakel nicht, dann wird…
Wie lautet die Definition der polynomiellen Hierachie (PH)?
Es sei Σ1\Sigma_1Σ1 := NP, Π1\Pi_1Π1 := co-NP und Δ1\Delta_1Δ1 := P. Für k ≥\geq≥ 1 sei Σk+1\Sigma_{k+1}Σk+1 := NP( Σk\Sigma_kΣk ) Πk+1\Pi_{k+1}Πk+1 := co- Σk\Sigma_kΣk Δk+1\Delta_{k+1}Δk+1 := P( Σk\Sigma_kΣk ) Die polynomielle Hierarchie PH ist die Vereinigung aller Σk\Sigma_kΣk , k ≥\geq≥ 1 Es ist auch konsistent, Σ0\Sigma_0Σ0 = Π0\Pi_0Π0 = Δ0\Delta_0Δ0 = P zu setzen und die Definition auf alle k ≥\geq≥ 0 auszudehnen.
Wie lautet der Beweis von Theorem 10.4.3 Ein Entscheidungsproblem L ist genau dann in Ek enthalten, wenn es ein Polynom p und ein Entscheidungsproblem L' ∈\in∈ P gibt, so dass mit A = {0, 1}p(lxl) gilt: L={x∣∃y1∈A∀y2∈A∃y3∈A...Qyk∈A:(x,y1,...,yk)∈L′}L=\{x | \exists y_1 \in A \forall y_2 \in A \exists y_3 \in A ... Q y_k \in A : (x, y_1,...,y_k) \in L' \}L={x∣∃y1∈A∀y2∈A∃y3∈A...Qyk∈A:(x,y1,...,yk)∈L′}
Beweisen durch Induktion über k, für k = 1 schon bewiesen. Beweis für k ≥\geq≥ 2 1. Teil: Wenn L die gegebene Form hat, können wir L durch eine nichtdeterministische Turingmaschine mit Orakel aus Σk−1\Sigma_{k-1}Σk−1 erkennen Eine nichtdeterministische Turingmaschine kann y1∈Ay_1 \in Ay1∈A nichtdeterministisch erzeugen Wir erlauben ihm als Orakel das Entscheidungsproblem L* L∗={(x,y1∣∃y2∈A∀y3∈A∃y4∈A...Qyk∈A:(x,y1,...,yk)∈L′ˉ}L^*=\{(x, y_1 | \exists y_2 \in A \forall y_3 \in A \exists y_4 \in…
Wie lautet der Beweis von Korollar 10.4.4. Ein Entscheidungsproblem ist genau dann in Πk\Pi_kΠk enthalten, wenn es ein Polynom p und ein Entscheidungsproblem L' ∈\in∈ P gibt, so dass mit A = {0, 1}p(lxl) gilt: L={x∣∀y1∈A∃y2∈A∀y3∈A...Qyk∈A:(x,y1,...,yk)∈L′}L=\{x | \forall y_1 \in A \exists y_2 \in A \forall y_3 \in A ... Q y_k \in A : (x, y_1,...,y_k) \in L' \}L={x∣∀y1∈A∃y2∈A∀y3∈A...Qyk∈A:(x,y1,...,yk)∈L′}
Ergibt sich durch die Anwendung der DeMorganschen Regeln auf das Ergebnis von Theorem 10.4.3.
Wie lautet der Beweis von Theorem 10.5.1. BPP ⊆\subseteq⊆ Σ2∩Π2\Sigma_2 \cap \Pi_2Σ2∩Π2 .?
Da BPP = Co-BPP muss nur noch BPP ⊆Σ2\subseteq \Sigma_2⊆Σ2 gezeigt werden ggb.: L ∈\in∈ BPP (durch probability amplification maximale Fehlerwahrscheinlichkeit bei Eingabe der Länge n: 2−(n+1)2^{-(n+1)}2−(n+1) Es soll eine Abschätzung p(n) / n ≤\leq≤ 2n erfolgen höchstens endlich vielen Eingaben für n, die diese Bedingung nicht erfüllen random. Alg. wird für diese Eingaben durch poly. Alg. auf allen Rechenwegen simuliert Grund: korrekte Resultat berechnen, ohne die Eigenschaft einer polynomiell…
Wie lautet die Definition der Komplexitätsklasse RP(L)?
Die Komplexitätsklasse RP(L) enthält für ein Entscheidungsproblern L alle Entscheidungsprobleme L', die sich durch RP Algorithmen mit Orakel L entscheiden lassen. Die Klasse RP( C\mathcal{C}C ) ist für eine Klasse C\mathcal{C}C von Entscheidungsproblemen die Vereinigung aller RP(L), L ∈C\in \mathcal{C}∈C . Analog werden ZPP(L), ZPP( C\mathcal{C}C ), BPP(L), BPP( C\mathcal{C}C ), PP(L) und PP( C\mathcal{C}C ) definiert.
Wie lautet der Beweis von Theorem 10.5.4. BPP(BPP) = BPP?
Sei L ∈\in∈ BPP(BPP) bzw. L ∈\in∈ BPP(L') mit dem BPP-Orakel L' Dann gibt es einen BPP-Rahmenalgorithmus A für L maximale Rechenzeit durch p1 beschränkt Fehlerwahrscheinlichkeit (prob amp) 1/6 Orakelalgorithmus A' für L' Fehlerwahrscheinlichkeit 1/(6* p1(|x|)) Orakelfrage wird durch Aufruf von A' ersetzt Resultierender Algorithmus arbeitet in polynomieller Zeit ohne Orakel zu benutzen Fehler, wenn A' oder A einen Fehler machen Fehlerwahrscheinlichkeit: p1(∣x∣)/6∗p1(∣x∣)+1/6=1/3p_1(|x|) / 6 * p_…
Wie lautet der Beweis von Korollar 10.5.5. NP ⊆\subseteq⊆ BPP ⇒\Rightarrow⇒ PH ⊆\subseteq⊆ BPP?
Es genügt die Beziehung Σk\Sigma_kΣk ⊆\subseteq⊆ BPP aus NP ⊆\subseteq⊆ BPP abzuleiten Das folgende Argument für k = 4 kann direkt auf allgemeines k übertragen werden. Aus NP ⊆\subseteq⊆ BPP und Theorem 10.5.4 (BPP(BPP) = BPP) folgt: Σ4\Sigma_4Σ4 = NP(NP(NP(NP))) ⊆\subseteq⊆ BPP(BPP(BPP(BPP))) ⊆\subseteq⊆ BPP(BPP(BPP)) ⊆\subseteq⊆ BPP(BPP) ⊆\subseteq⊆ BPP
Wie lautet der Beweis von Theorem 10.5.6. NP ⊆\subseteq⊆ BPP ⇒\Rightarrow⇒ NP = RP?
Nach Definition ist RP ⊆\subseteq⊆ NP Es muss nur noch NP ⊆\subseteq⊆ RP aus NP ⊆\subseteq⊆ BPP gefolgert werden NPC Problem L aus NP ⊆\subseteq⊆ BPP folgern, dass L ∈\in∈ RP ist Für den Beweis werden 3 Arten vom Knotenfärbungsproblem benötigt: GC: Färbung der Knoten in k Farben möglich? LEX-GC: Färbung repräsentiert als Vektor f(G), auf dem eine Lexikografische Ordnung ausgeführt werden kann MIN-GC: Entscheidung, ob ein Vektor c kleiner als f(G) ist GC lässt sich auch wie folgt Darstellen und…
Wie lautet die Definition eines interaktives Beweissystems?
Ein interaktives Beweissystem (interactive proof system) besteht aus einem Kommunikationsprotokoll zwischen zwei Parteien B (Bob) und V (Victoria) und zugehörigen randomisierten Algorithmen. Das Kommunikationsprotokoll regelt, wer die erste Nachricht sendet. Nach einer eventuell von der Eingabe und vom Zufall abhängigen Anzahl von Kommunikationsrunden entscheidet Victoria, ob die Eingabe akzeptiert wird. Die Rechenzeit von Victoria ist polynomiell in der Eingabelänge beschränkt. Wir bezeichnen…
Wie lautet die Definition der Komplexitätsklasse IP?
Ein Entscheidungsproblem L gehört zur Komplexitätsklasse IP, wenn es ein Kommunikationsprotokoll K und einen randomisierten polynomiell zeitbeschränkten Algorithmus V mit folgenden Eigenschaften gibt: Es gibt einen randomisierten Algorithmus B, so dass für alle x∈Lx \in Lx∈L die Bedingung Prob(DB,V = 1) ≥\geq≥ 3/4 erfüllt ist Für alle randomisierten Algorithmen B und x∉Lx \notin Lx∈/L ist die Bedingung Prob(DB,v(x) = 1) ≤\leq≤ 1/4 erfüllt. Ein Problem L ∈\in∈ IP gehört zu IP(k), wenn das zugehö…
Wie lautet der Beweis von Theorem 11.3.1. GIˉ∈\bar{GI} \inGIˉ∈ IP(2)?
Eingabe: 2 Graphen (G0 und G1) mit gleicher Knotenmenge (V1 = V2 = {1, ..., n} Bob und Victoria nutzen folgendes interaktives Beweissystem: Victoria erzeugt zufällig i ∈\in∈ {0, 1} und Permutation π∈\pi \inπ∈ Sn, berechnet H = π\piπ (Gi) und sendet H an Bob Bob berechnet ein j ∈\in∈ {0, 1} und sendet es an Victoria. Sind G0 und G1 nicht isomorph ist H nur zum Graphen Gi isomorph Bob kann dann einfach i berechnen, indem er alle Permutationen auf den beiden Graphen testet Victoria akzeptiert (G0,…