Teoria złożoności obliczeniowej

Problemy obliczeniowe

Obliczeniowy problem decyzyjny.

Może być przedstawiony jako j_{}ezyk L ⊆ Σ^{∗}.

Przykłady

• Liczby pierwsze {w ∈ {0, 1}^{∗} : w jest binarnym przedstawieniem liczby pierwszej}

• Grafy ze ścieżk_{}a Hamiltona

{w ∈ {0, 1}^{∗} : |w| = n^{2} dla pewnego n i
∃1 ≤ a_{1}, …, a_{n} ≤ n

w_{n·a_{i}+a_{i+1}} = 1 dla i = 1, …, n − 1}

Obliczeniowy problem funkcyjny.

Może być przedstawiony jako funkcja f : Σ^{∗} → Γ^{∗}.

Klasy złożoności

Czasowa złożoność wielomianowa: P

Problem L ⊆ Σ^{∗} jest w klasie P jeśli istnieje maszyna Turinga M i stała k taka, że L = L(M) i dla każdego w maszyna M wykonuje ≤ |w|^{k} kroków.

Czasowa niedeterministyczna złożoność wielomianowa: NP

Problem L ⊆ Σ^{∗} jest w klasie NP jeśli istnieje j_{}ezyk R ⊆ Σ^{∗}$Σ^{∗} w klasie P i stała k, takie że

L = {w : (∃v ∈ Σ^{∗}) w$v ∈ R ∧ |v| ≤ |w|^{k}}

Równoważnie: L = L(M) dla pewnej niedeterministycznej maszyny Turinga działaj_{}acej w czasie wielomianowym.

Pami_{}eciowa złożoność wielomianowa: PSPACE

Problem L ⊆ Σ^{∗} jest w klasie PSPACE jeśli istnieje maszyna Turinga M i stała k taka, że L = L(M) i dla każdego w maszyna M odwiedza ≤ |w|^{k} komórek pami_{}eci.

Wiadomo:

P ⊆ NP ⊆ PSPACE

Hipoteza:

P ≠ NP ≠ PSPACE

Klasa funkcji obliczalnych w czasie wielomianowym: FP

Funkcja f : Σ^{∗} → Γ^{∗} jest w klasie FP jeśli istnieje stała k i maszyna Turinga M obliczaj_{}aca f(w) w ≤ |w|^{k} krokach (w szczególności |f(w)| ≤ |w|^{k}).

Redukcje pomi_{}edzy problemami

Problem A ⊆ Σ^{∗} redukuje si_{}e do problemu B ⊆ Γ^{∗} w czasie wielomianowym (w sensie Karpa) jeśli istnieje funkcja f : Σ^{∗} → Γ^{∗} w klasie FP (redukcja), taka, że, dla każdego w ∈ Σ^{∗},

w ∈ A ⇔ f(w) ∈ B

Problemy NP–zupełne

Problem L jest NP–zupełny jeśli:

1. L ∈ NP,

2. każdy problem M ∈ NP redukuje si_{}e do L w czasie wielomianowym.

Przykłady problemów NP–zupełnych:

• SAT — problem spełnialności formuł Boole’owskich (twierdzenie Cooka).

• 3–CNF–SAT — problem spełnialności formuł Boole’owskich w postaci koniunkcyjno–dyzjunkcyjnej, gdzie każda koniunkcja ma 3 literały.

• Problem spełnialności sieci logicznych.

• Grafy Hamiltonowskie.

• Pary ⟨G, k⟩, takie, że graf G można pokolorować k kolorami.

• Grafy kolorowalne 3 kolorami.

• Grafy planarne kolorowalne 3 kolorami.

• Problem plecakowy: układ liczb M, a_{1}, …, a_{n} (danych w postaci binarnej), takich, że istniej_{}a β_{1}, …, β_{n} ∈ {0, 1}, takie że

M = β_{1} · a_{1} + … + β_{n} · a_{n}