# [Zap] 20.1.2011

<{ForumPost(poster="netsir", timestamp=2011-01-20 10:15:11)}>
Zapocet probihal ve stejnym duchu jako obvykle, otazky tentokrat byly:

* 1) TS prijimajici jazyk a<sup>n</sup>b<sup>n</sup>c<sup>n</sup>.  
2) PRF sign(x).  
3) Dokazte, ze Batoh je NP-uplny.  
4) Ukazte, ze splnitelnost HORN-SAT patri do P.

<{/ForumPost}>

<{ForumPost(poster="oskee", timestamp=2011-01-20 11:26:07)}>
Ja by som len dodal nastin riesenia ulohy 4) (tie prve 3 by mali byt bezproblemove, respektive ich riesenia najdete roztrusene v topicu), pretoze vacsina ludi, s ktorymi som sa potom bavil, s tym mala problem. Ja sam som to nemal cele, ale Kucera prehlasil, ze som bol na polceste  :wink:   
  
Cize - HORN-SAT - test splnitelnosti hornovskej KNF (taka, ktora ma v kazdej klauzuli najviac 1 kladny literal) v polynomialnom case.  
  
1) vsetky literaly nastavime na 0. Tym mame zarucene pravdive vsetky klauzule, ktore su bez kladneho literalu.  
2) prejdeme klauzule obsahujuce len jeden kladny literal a tieto nastavime na 1.  
3) tu som skoncil v domneni, ze to staci, Kucera mi vsak povedal ze nie a snazil sa sformulovat nejaky protipriklad, ale po chvili to vzdal, pretoze tam cakali dalsi ludia na opravenie. Povedal vsak nieco o tom, ze to zlyha na nejakom pripade, kde je v KNF nejaka klauzula, kde su 2 literaly, kladny a zaporny a ten zaporny je potom ako samostatna kladna klauzula niekde inde; takze je treba spravit este nejaky jeden korekcny prechod - aky, to neviem, ale aspon som vas varoval, ze 1) a 2) nestaci  8)   
  
Este poznamka k casu na test, pretoze som to nikde nenasiel - je ho priblizne tolko, co na skusku, cize cca 1.5-2h.
<{/ForumPost}>

<{ForumPost(poster="ucm", timestamp=2011-01-21 12:49:31)}>
Pro problem ekv. HORN SATU (<= 1 negativni literal v konjunkco):  
  
1. najdi konjunkci, ktera obsahuje pouze negativni literal a zadny pozitivni. Pokud neni, tak jdi na 6.  
2. Promenna X v konjunkci musi byt 0 (jinak by konjunkce byla 0 a tedy cela formule by byla 0)  
3. Odtran konjunkci z formule (uz o ni vime hodnotu, jenom by prekazela)  
4. Najdivsechny konjunkce, ktere obsahuji formulis promennou X a zjisti, jak to s nimi je (= dej do prom v konjunkci hodnotu 0 a zjisti, jak to ovlivni hodnotu konjunkce).   
4.1 Pokud konjunkce obsahuje pouze 1 pozitivni literal X, tedy konjunkce je (X), tak je to spor, a formule nema splnitelne reseni  
4.2 Pokud konjunkce obsahuje not X, tak je pravdiva a konjunkci muzeme odstranit  
4.3 ...nechce se mi to sem vsechno psat, ale proste do konjunkce dosadite nutnou hodnotu a spoctete, jak vypada nova konjunkce, zda jeste muze byt pravdiva, zda je nezbytna atd.  
5. Pokud existuje konjunkce s prave 1 negativnim literalem, jdi na 1.  
6. Nyni mame pouze konjunkce s alespon 1 pozitivnim literalem, takze kdz do vsech zbyvajicich promennych dosadime 1, tak i formule bude 1 a formule je tedy splnitelna
<{/ForumPost}>