Příklady NP-úplných problémů, dokazování NP-úplnosti

Konkrétní polynomiální redukce

$SAT{\le }_{p}3-SAT{\le }_{p}I{S}_{DEC}{\le }_{p}V{C}_{DEC}{\le }_{p}HC{\le }_{p}HK{\le }_p△-TS{P}_{DEC}{\le }_{p}TS{P}_{DEC}$

SAT (problém splnitelnosti booleovských formulí)

Název: SAT Vstup: Booleovská formule v konjuktivní normální formě. Otázka: Je daná formule splnitelná?

3-SAT (problém SAT s omezením na 3 literály)

Název: 3-SAT Vstup: Booleovská formule v konjunktivní normální formě, kde v každé klauzuli jsou právě 3 literály. Otázka: Je daná formule splnitelná?

IS_{DEC} (problém nezávislé množiny [Independent Set])

Název: IS${}_{DEC}$ Vstup: Neorientovaný graf $G$ (o $n$ vrcholech); číslo $k$ ($k\le n$). Otázka: Existuje v $G$ nezávislá množina velikosti $k$? (tj. množina $k$ vrcholů, z nichž žádné dva nejsou spojeny hranou)

VC_{DEC} (vrcholové pokrytí [Vertex Cover])

Název: VC${}_{DEC}$ Vstup: Neorientovaný graf $G$ (o $n$ vrcholech); číslo $k(k\le n)$. Otázka: Existuje v $G$ vrcholové pokrytí velikosti $k$? (tj. množina vrcholů, v níž má každá hrana aspoň jeden konec)

HC (problém hamiltonovského cyklu)

Název: HC Vstup: Orientovaný graf $G$. Otázka: Existuje v $G$ hamiltonovský cyklus? (tj. uzavřená cesta, procházející každým vrcholem právě jednou)

HK (problém hamiltonovské kružnice)

Název: HK Vstup: Neorientovaný graf $G$. Otázka: Existuje v $G$ hamiltonovská kružnice? (tj. uzavřená cesta, procházející každým vrcholem právě jednou)

TSP_{DEC} (problém obchodního cestujícího)

Název: TSP${}_{DEC}$ Vstup: Množina “měst” $\{1,2,...,n\}$, přirozená čísla (“vzdálenosti”) $d_{ij}(i=1,2,...,n,j=1,2,...,n)$, kde $d_{ii}=0$ a $d_{ij}=d_{ji}$; dále číslo $l$ (“limit”). Otázka: Existuje “okružní jízda” dlouhá nejvýše $l$, tj. existuje permutace $(i_1,i_2,...,i_n)$ množiny $\{1,2,...,n\}$ tak, že $d(i_1,i_2)+d(i_2,i_3)+...+d(i_{n-1},i_n)+d(i_n,i_1)\le l$?

• $△-TSP$ je podproblém problému TSP, v němž každá instance splňuje trojúhelníkovou nerosnost (tedy $d(i,j)\le d(i,k)+d(k,j))$

---

SAT \leq_{p} 3-SAT

1. Sestavím booleovský obvod
2. Vypíšu pravidla, jaká musí booleovský obvod splňovat
3. Uplatním na ně De Morganovy zákony

3-SAT \leq_{p} IS_{DEC}

1. Udělám $3$ vrcholy pro každou klauzuli ve formuli a spojím je. (Udělám trojúhelníky)
2. Vrchol s proměnnou $x$ propojím s vrcholem negací proměnné $x$
3. Číslo $k$ je počet klauzulí ve formuli

IS_{DEC} \leq_{p} VC_{DEC}

• V grafu $G=(V,E)$ je $V^{\prime }$ nezávislá množina právě tehdy, když $V$ \ $V^{\prime }$ je vrcholové pokrytí.

VC_{DEC} \leq_{p} HC

• Pro (neorientovaný) graf $G=(V,E)$ a číslo $k$ jsme sestrojili graf $G^{\prime }=(V^{\prime },E^{\prime })$ postupně takto:
  • Pro každý vrchol $v\in V$ grafu $G$, se stupněm $deg(v)$, zařadíme do $G^{\prime }$ “řetízek” vrcholů $v_1\to v_2\to ...\to v_{2\cdot deg(v)}$ (šipky označují příslušné hrany v $G^{\prime }$)
  • Pro dané číslo $k$ zařadíme do $G^{\prime }$ navíc vrcholy $u_1,u_2,...,u_k$ a pro každé $i\in [1,k]$ a každý vrchol $v\in V$ s nenulovým stupněm přidáme do $G^{\prime }$ hrany $u_i\to v_1$ a $v_{2\cdot deg(v)}\to u_i$ (z $u_i$ lze tedy “skočit” na začátek libovolného “řetízku” a z konce libovolného “řetízku” lze zase skočit na $u_i$, pro každé $u_i\in \{u_1,u_2,...,u_k\}$);
  • Pro každý vrchol $v\in V$ grafu $G$ očíslujeme jeho incidentní hrany čísly $1,2,...,deg(v)$ a pro každou hranu $e=\{v,v^{\prime }\}\in E$ grafu $G$ přidáme do $G^{\prime }$ čtyři hrany $e$ vzhledem k $v^{\prime }$; pak přidáme hrany $v_{2l-1}\leftrightarrow v_{{}^{\prime }2l^{\prime }-1}$ a $v_{2l}\leftrightarrow v_{{}^{\prime }2l^{\prime }}$ (kde $x\leftrightarrow y$ reprezentuje dvojici hran $x\to y$ a $y\to x$).

HC \leq_{p} HK

• Místo každého vrcholu přidám $3$ vrcholy (začátek, střed, konec), které propojím podle orientace hran v grafu HC

HK \leq_{p} \triangle - TSP_{DEC}

• V grafu $G=(V,E)$ jsme každé hraně přiřadili hodnotu (délku) $1$ a pak jsme doplnili hrany tak, aby vznikl úplný graf, každé doplněné hraně jsme přiřadili hodnotu $2$.

Navigace

Předchozí: Cook-Levinova věta Následující: Třída PSPACE, její vztah k třídám P a NP, PSPACE-úplné problémy Celý okruh: 1. Teoretické základy informatiky