Seminar: Logik und Komplexität

Seminar: Logik und Komplexität
von: Thomas Zeume
1 Logiken
1.1 Aussagenlogik
Problem:
p−W SAT (Φ)
(Gewichtetes, parametrisiertes Erfüllbarkeitsproblem zur Klasse Φ).
Gegeben ϕ ∈ Φ und k ∈ N. Parameter sei k. Ist φ k-erfüllbar? D.h. gibt es eine erfüllende Belegung in der
k Variablen wahr sind?
Denition.
P ROP := {ϕ | ϕ ist aussagenlogische Formel }
Denition (Eine Hierarchie von Formeln der Aussagenlogik).
Γ0,d := {λ1 ∧ . . . ∧ λc | c ∈ [d], λ1 , . . . , λc Literale }, ∆0,d := {λ1 ∨ . . . ∨ λc | c ∈ [d], λ1 , . . . , λc Literale }
V
Γt+1,d := { i∈[d] δi | d ∈ N und δi ∈ ∆t,d für alle i ∈ [d]}
W
∆t+1,d := { i∈[d] δi | d ∈ N und δi ∈ Γt,d für alle i ∈ [d]}
Lemma.
p−W SAT (Γ1,1 ) ≤f pt
≤f pt p−W SAT (Γ2,1 ) ≤f pt p−W SAT (Γ3,1 )
p−W SAT (Γ1,2 )
.
.
.
≤f pt p−W SAT (P ROP ) ≤f pt p−W SAT (CIRC)
1.2 Prädikatenlogik
Denition (Struktur). Sei τ Menge von Relationssymbolen R, jedes mit festgelegter Stelligkeit s(R). Eine
τ -Struktur A besteht aus einem Universum A und einer Interpretation, die jedem Relationssymbol R in
τ eine Relation RA ⊆ As(R) zuordnet. Hier: Nur endliche Universen und Mengen von Relationssymbolen.
Denition (Semantik). Bestimme induktiv erfüllende Tupel ϕ(A) über dem Universum. Beispielsweise
• Falls ϕ(x, y) = Rxy , dann ϕ(A) := {(ax , ay ) ∈ A2 | (ax , ay ) ∈ RA }
• Falls ϕ(x, y) = φ(x, y) ∧ ψ(x, y), dann
ϕ(A) := {(ax , ay ) ∈ A2 | (ax , ay ) ∈ φ(A) und (ax , ay ) ∈ ψ(A)}
• Falls ϕ(x) = ∃yφ(x, y), dann ϕ(A) := {(ax )| es gibt ein ay ∈ A mit (ax , ay ) ∈ φ(A)}
Notation: A |= ϕ(a1 , a2 ) anstelle (a1 , a2 ) ∈ ϕ(A)
Beispiel. (a) Graph-Struktur. Die Symbolmenge τgraph bestehe aus dem binären Relationssymbol E .
Deniere τgraph -Struktur G = (G, E G ), wobei G die Menge der Knoten und E G ⊆ G2 die Menge der
Kanten ist.
(b) Logische Charakterisierung von V ERT EX − COV ER:
vc0k (x1 , . . . , xk ) := ∀y∀z Eyz →
_
(xi = y ∨ xi = z)
i∈[k]
vck := ∃x1 . . . ∃xk
^
xi 6= xj ∧ vc0k (x1 , . . . , xk )
1≤i<j≤k
Denition (Eine Hierarchie von Formeln der Prädikatenlogik).
Formeln in Σt+1 sind von der Form ∃x1 . . . ∃xk ϕ mit ϕ ∈ Πt
Formeln in Πt+1 sind von der Form ∀x1 . . . ∀xk ϕ mit ϕ ∈ Σt
Σ0 und Π0 sind Formeln erster Stufe ohne Quantizierung
1
1.3 Logik zweiter Stufe
• Quantizierung auch über Relationen erlaubt
Beispiel: Logische Charakterisierung der k-Färbbarkeit von Graphen. Seien X1 , . . . , Xk Relationsvariablen der Stelligkeit 1.
colk := ∃X1 . . . ∃Xk ∀x∀y
_
_
Xi x ∧
^ ¬ Xi x ∧ Xj x ∧
Exy → ¬ Xi x ∧ Xi y
1≤i<j≤k
i∈[k]
i∈[k]
Denition (Eine Hierarchie von Formeln der zweiten Stufe).
Formeln in Σ1t+1 sind von der Form ∃X1 . . . ∃Xk ϕ mit ϕ ∈ Π1t
Formeln in Π1t+1 sind von der Form ∀X1 . . . ∀Xk ϕ mit ϕ ∈ Σ1t
Σ10 und Π10 sind Formeln zweiter Stufe ohne Quantizierung
2 Komplexität der Logiken erster und zweiter Stufe
2.1 Komplexität der Probleme Evaluation und Model-Checking
Sei Φ Klasse von Formeln.
Problem: EV AL(Φ) (Evaluation). Gegeben eine Struktur A und eine Formel ϕ ∈ Φ. Berechne ϕ(A)!
Problem: M C(Φ) (Model-Checking). Gegeben eine Struktur A und eine Formel ϕ ∈ Φ. Gilt A |= ϕ?
Problem: p−M C(Φ) (parametrisiertes Model-Checking). Gegeben eine Struktur A und eine Formel
ϕ ∈ Φ. Parameter sei |ϕ|. Gilt A |= ϕ?
Satz.
EV AL(F O)
und
M C(F O)
Anzahl freier Variablen der Subformeln der
Korollar.
Dann sind
O(|ϕ| · |A|ω · ω)
Eingabeformel ϕ ist.
können in Zeit
gelöst werden, wobei
ω
die maximale
k ≥ 1 und F Ok die Teilklasse von F O, die Formeln mit maximal k Variablen enthält.
EV AL(F Ok ) und M C(F Ok ) in polynomieller Zeit lösbar. Insbesondere sind EV AL({ϕ}) und
Sei
M C({ϕ})
polynomiell lösbar.
Korollar.
p−M C(Φ) ∈ XP
2.2 Fagin-Beschreibbarkeit (Fagin-denability)
Satz (Satz von Fagin).
Σ11
Ein Entscheidungsproblem ist in
NP
genau dann wenn es mit einer Formel aus
beschrieben werden kann.
Sei ϕ(X1 , . . . , Xk ) Formel der Prädikatenlogik mit freien Relationsvariablen X1 , . . . , Xk .
Problem: F Dϕ (Fagin-beschreibbar mit ϕ). Gegeben eine Struktur A. Gibt es eine Lösung für ϕ in
A?
Sei ϕ(X) Formel der Prädikatenlogik mit einer freien Relationsvariablen X .
Problem: W Dϕ (Gewichtet Fagin-beschreibbar mit ϕ). Gegeben eine Struktur A und k ∈ N. Gibt
es eine Lösung S ⊆ As für ϕ mit |S| = k?
3 Polynomialzeithierarchie
Satz.
Satz.
Für alle
k≥1
ist
Für alle
k≥1
ist das Problem
ASATk
vollständig für den
M C(Σk )
k -ten
Level
ΣP
k
vollständig für den
der Polynomialzeithierarchie.
k -ten
Level
ΣP
k
der Polynomialzeithier-
archie.
Satz (Verallgemeinerung von Fagin's Satz).
Für alle
k ≥1
ist ein Entscheidungsproblem in
1
dann wenn es mit einer Formel aus Σk beschrieben werden kann.
2
ΣP
k
genau

Download Report