Matematické Fórum

Lordikcz

Ahoj chci dokázat NP-úplnost hamiltonovi cesty,ale mám problémy s pochopením widgetů z knihy Michael Sipser Introduction to the theory of computation..

Jedná se zde o redukci z jazyka 3SAT na graf Hamiltonovi cesty.
3Sat je jazyk splnitelných booleovských formulí ve třetí konjunktivní normální formě.

Takže v podstatě jde o to nějakou formuli například ve tvaru: $(a\vee b \vee \bar{c})\wedge (\bar{a}\vee b \vee c)$

redukovat na graf Hamiltonovi cesty pokud je formule splnitelná a pokud není splnitelná ,tak výsledný graf neobsahuje Hamiltonovu cestu.

Hamiltonova cesta je v grafu taková cesta ,která začne ve vrcholu S, projde všechny další vrcholy právě jednou a skončí ve vrcholu T.

Už se tu konstrukci toho grafu snažím pochopit dva dny,ale pořád v tom mám nějaké nesrovnalosti a byl bych Vám moc vděčný za jakoukoliv pomoc :-)

Odkaz na knihu:
Odkaz kapitola 7.35 strana 276

FailED · 02. 12. 2011 22:12

Ahoj,

jaký krok v tom důkazu nechápeš?

"Orientace toho grafu zaručuje, že se proměnné budou procházet postupně. Směr procházení proměnné odpovídá jejímu ohodnocení. Vrchol odpovídající klauzuli můžeme projít jen v případě, že je splněna (díky ohodnocení nějaké její proměnné)."

Lordikcz · 03. 12. 2011 00:13

↑ FailED:↑ FailED:

Ahoj, konkrétně mi není jasné kolik těch diamantových struktur odpovídajících proměnným bude.

$(a\vee b \vee \bar{c})\wedge (\bar{a}\vee b \vee c)$

Řekl bych že v tomto případě jich bude 6,protože mám 6 literálů jen mi v tomto případě zase není jasné proč by v řádcích diamantu mělo být 3k+1 uzlů,protože by takto jeden diamant zastoupil jeden literál a tento jeden literál je v každé clausuli jen 1x takže by mi měly stačit v řádku 4 uzly (dva pro objížďku přes uzel clausule a dva krajní).

Moc díky :-)

FailED · 03. 12. 2011 00:28

↑ Lordikcz:

Je tam jeden ten diamant za každou proměnnou, ne za literál. Budou tam 3, ohodnocení se pozná podle toho, ze které strany na ten diamant přijdem.

V řádcích těch diamantů je 3k+3 uzlů, je to tam proto, aby se oddělily ty dvojice uzlů, ze kterých vedou hrany do klauzulí.

Lordikcz · 03. 12. 2011 09:52

↑ FailED:

Jo a ještě tedy poslední věc pro jednu proměnnou mám tedy jeden diamant ,takže pro $a$ a $\bar{a}$ bude jeden diamant.

Třeba pokud bych proměnné $a$ přiřadil ohodnocení 1,tak vyjdu z vrcholu S a teď si mám vybrat jestli půjdu vpravo nebo vlevo,ale mám použít $a$ nebo $\bar{a}$ ? Asi bych řekl ,že se mám řídit ohodnocením co jsem přiřadil a to jestli je proměnná $\bar{a}$ mi ovlivní jen to v jakém směru budu procházet objížďku přez uzel clausule.

FailED · 04. 12. 2011 20:44 — Editoval FailED (04. 12. 2011 20:47)

Pokud a je prvovýrok (výroková proměnná), $\bar{a}$ značí literál typu $\neg a$ .

Když má výroková proměnná $a$ ohodnocení $v(a)$ , výrok $a$ má ohodnocení $v(a)$ a výrok $\bar{a}$ ohodnocení $-v(a)$ .

Lordikcz · 04. 12. 2011 21:05

↑ FailED:↑ FailED:

Jo jasně myslím ,že tohle chápu prostě pokud je $v(a)=1$ pak $v(\bar{a})=0$ ..

Ale nerozumím tomuto:

Ta formule co jsem uvedl má dvě clausule v jedné je $a$ a v druhé se vyskytuje $\bar{a}$ .

K těmto dvou klausulím mám celkem tři diamanty,kde jeden z nich odpovídá proměnné $a$ a z toho co jsem pochopil,tak by z něj měli vést dvě objíždky přez uzle clausulí. Jedna objížďka pro $a$ a druhá pro $\bar{a}$ .

Řekněme ,že diamant pro proměnnou $a$ je první mám se tedy z prvního uzlu vydat doprava nebo doleva?
Kterým ohodnocením se mám řídit, když v jedné clausuli je má tato proměnná ohodnodnocení $v(a)$ a v druhé $v(\bar{a})$ .

Ještě tedy vycházím z ohodnocení, které přiřadím proměnným ve formuli tak, aby byla splnitelná.

FailED · 06. 12. 2011 00:36 — Editoval FailED (06. 12. 2011 00:44)

↑ Lordikcz:

Při ohodnocení proměnných $v$ má proměnná $a$ ohodnocení $v(a)$ .

$\bar{a}$ není proměnná, ale literál (výroková formule) $\neg a$ , která má shodou okolností (podle definice ohodnocování formulí) ohodnocení $-v(a)$ .

Formule $\varphi$ je splnitelná, když existuje ohodnocení proměnných $v$ takové, že $v \models \varphi$ .

Nejdřív si nastuduj základní pojmy, bez toho to v logice nepůjde.

Matematické Fórum

#1 02. 12. 2011 18:41 — Editoval Lordikcz (02. 12. 2011 18:48)

Důkaz NP úplnosti Hamiltonovy cesty

#2 02. 12. 2011 22:12

Re: Důkaz NP úplnosti Hamiltonovy cesty

#3 03. 12. 2011 00:13

Re: Důkaz NP úplnosti Hamiltonovy cesty

#4 03. 12. 2011 00:28

Re: Důkaz NP úplnosti Hamiltonovy cesty

#5 03. 12. 2011 09:52

Re: Důkaz NP úplnosti Hamiltonovy cesty

#6 04. 12. 2011 20:44 — Editoval FailED (04. 12. 2011 20:47)

Re: Důkaz NP úplnosti Hamiltonovy cesty

#7 04. 12. 2011 21:05

Re: Důkaz NP úplnosti Hamiltonovy cesty

#8 06. 12. 2011 00:36 — Editoval FailED (06. 12. 2011 00:44)

Re: Důkaz NP úplnosti Hamiltonovy cesty

Zápatí