Informatik Grundlagen – Komplexitätstheorie und P-NP
Karteikarten zum Thema „Informatik“ · 14 Karten · von atrio. Beispiele: Was definiert die Komplexitätsklasse P? · Was definiert die Komplexitätsklasse NP?
Karten
14 KartenWas definiert die Komplexitätsklasse P?
Rückseite
P enthält alle Entscheidungsprobleme, die eine deterministische Turingmaschine in polynomieller Zeit O(n^k) lösen kann.
Was definiert die Komplexitätsklasse NP?
Rückseite
NP enthält alle Entscheidungsprobleme, deren Lösungen eine deterministische Turingmaschine in polynomieller Zeit verifizieren kann.
Was bedeutet NP-vollständig?
Rückseite
Ein Problem ist NP-vollständig, wenn es in NP liegt und jedes Problem in NP polynomiell darauf reduzierbar ist.
Was bedeutet NP-schwer?
Rückseite
Ein Problem ist NP-schwer, wenn jedes Problem in NP polynomiell darauf reduzierbar ist – es muss nicht in NP liegen.
Was ist eine polynomielle Reduktion?
Rückseite
Eine Funktion f, die in polynomieller Zeit berechenbar ist und x ∈ L₁ genau dann gilt, wenn f(x) ∈ L₂ – zeigt L₁ ≤ₚ L₂.
Was besagt der Cook-Levin-Satz?
Rückseite
SAT (Erfüllbarkeit boolescher Formeln) ist NP-vollständig – das erste bewiesene NP-vollständige Problem, Basis für alle weiteren NP-Vollständigkeitsbeweise.
Warum ist SAT das zentrale NP-vollständige Problem?
Rückseite
Cook-Levin zeigt: Jede nichtdeterministische polynomielle Berechnung lässt sich als boolesche Formel kodieren, deren Erfüllbarkeit der Akzeptanz entspricht.
Nenne drei klassische NP-vollständige Probleme.
Rückseite
Zu den klassischen NP-vollständigen Problemen zählen Traveling Salesman, Knapsack, 3-SAT, Knotenüberdeckung, Hamiltonkreis und Graphenfärbung – jeweils als Entscheidungsversion.
Unterscheide Entscheidungs- und Optimierungsproblem am Beispiel Traveling Salesman.
Rückseite
Entscheidung: 'Gibt es eine Tour ≤ k?' (in NP). Optimierung: 'Finde kürzeste Tour' (NP-schwer, nicht in NP ohne Zertifikat).
Was ist eine nichtdeterministische Turingmaschine?
Rückseite
Theoretisches Modell, das bei mehreren Übergängen alle Pfade parallel erkundet – akzeptiert, wenn mindestens ein Pfad akzeptiert. Definiert NP als Laufzeitklasse.
Was besagt der Zeithierarchie-Satz?
Rückseite
Für zeitkonstruierbare f: DTIME(o(f(n))) ⊊ DTIME(f(n) log f(n)) – mehr Zeit ermöglicht strikt mehr Probleme zu lösen.
Was ist der Zusammenhang zwischen P, NP und PSPACE?
Rückseite
P ⊆ NP ⊆ PSPACE ⊆ EXP – ob P = NP oder NP = PSPACE gilt, ist offen; P ≠ EXP ist bewiesen.
Warum ist P ≠ NP relevant für Kryptographie?
Rückseite
Viele Kryptosysteme (RSA, ECC) setzen voraus, dass bestimmte Probleme (Faktorisieren, diskreter Logarithmus) nicht in P liegen – P = NP bräche sie.
Was bedeutet der Satz von Ladner, falls P ≠ NP?
Rückseite
Dann existieren Probleme in NP, die weder in P noch NP-vollständig sind – die Klasse NP-intermediate ist nicht leer.