Rešitev: KLIKA

Iz MaFiRaWiki

\bullet Ali je KLIKA sploh odločitveni problem?
P: (G,k), kjer je G graf in k \in \mathbb{N}
V: Ali graf G vsebuje KLIKO velikosti k?
O: DA ali NE
\Longrightarrow KLIKA je res odločitveni preblem


\bullet KLIKA \in \mathcal{NP}
Ali obstaja NTS, ki v polinomskem času reši problem KLIKE?
Naj bo M TS, ki na primeru (G,k) problema KLIKE deluje na naslednji način:
M začne kot NTS in izbere k vozlišč v G, ki naj bi določali KLIKO velikosti k.
Nato začne kot DTS in ugotavlja, ali obstaja povezava med vsakim parom izbranih k vozlišč.
Če povezava obstaja potem v G obstaja KLIKA velikosti k, v nasprotnem primeru pa izbere druga vozlišča in ponovi postopek.
M je v polinomskem času zapletena zadeva.
\Longrightarrow M je NTS, ki v polinomskem času reši problem KLIKE
\Longrightarrow KLIKA \in \mathcal{NP}


\bullet SAT \propto KLIKA
izjava sestavljena iz k stavkov je resnična \Longleftrightarrow graf ima KLIKO velikosti k
Literali k stavkov postanejo vozlišča grafa, množica resničnih literalov pa mora narediti KLIKO velikosti k v grafu, ki ga gradimo.
Nato bo resnična izjava, ki jo naredi vsaj en resničen literal na stavek povzročila, da se bo v grafu pojavila KLIKA velikosti k.
Naj bo vsak literal v vsakem stavku vozlišče grafa, ki ga gradimo.
Želimo, da bi nam uspelo povezati resnične literale, toda ne po dva iz istega stavka.
In dva, ki sta drug drugemu negacija, ne moreta biti resnična hkrati.
Torej povežemo vse literale, ki niso v istem stavku in niso negacija drug drugega.
Gradimo graf G = (V,E), v katerem velja:
V= \{ <x_{i}, s_{j}>; x_{i} \in s_{j} \}, kjer x_{i} \in s_{j} pomeni, da je spremenljivka xi v stavku sj
E= \{ (<x_{i}, s_{j}>, <x_{k}, s_{l}>); x_{i} \neq \neg x_{k} \wedge s_{j} \neq s_{l} \}
(\Longrightarrow):
Če je izjava sestavljena iz k stavkov resnična, potem je resničen vsak izmed k stavkov in zato v vsakem stavku obstaja literal, ki je resničen.
To je ravno KLIKA, ker množica resničnih literalov, kjer vsak prihaja iz enega stavka, ne more vsebovati nekega literala in njegove negacije in vsi literali so povezani drug z drugim, ker smo povezali literale, ki so v različnih stavkih.
(\Longleftarrow):
Ker ima graf KLIKO velikosti k, mora teh k vozlišč prihajati iz različnih stavkov, ker nobena dva literala iz istega stavka nista povezana.
Velja pa tudi, da noben literal in njegova negacija nista v KLIKI.
Tedaj so lahko vsi literali v KLIKI resnični in ti nam dajo renično izjavo.

Osebna orodja