Diferente pentru 2-sat intre reviziile #38 si #39

Nu exista diferente intre titluri.

Diferente intre continut:

h3. Soluţie
Dacă între două noduri există muchie atunci nu pot fi amândouă în mulţimea $I$, iar dacă între două noduri nu există muchie nu pot fi amândouă în mulţimea $C$.
Transformăm această problemă într-o instanţă de $2SAT$ astfel: faptul că nodul <tex> x </tex> aparţine mulţimii $C$ îl reprezentăm dândui lui <tex> x </tex> valoarea <tex> 1 </tex>, iar apartenenţa mulţimii $I$ se codifică prin valoarea <tex> 0 </tex>. Acum existenţa unei muchii <tex> (x, y) </tex> corespunde expresiei <tex> x \vee y </tex>, astfel cel puţin unul din nodurile <tex> x </tex> şi <tex> y </tex> nu va fi în mulţimea $I$. Dacă nu există muchia <tex> (x, y) </tex> putem scrie <tex> \sim x \vee \sim y </tex>, această expresie va fi adevărată dacă cel puţin un nod din cele două nu va fi în mulţimea $C$.
Dacă între două noduri există muchie atunci nu pot fi amândouă în mulţimea <tex> I </tex>, iar dacă între două noduri nu există muchie nu pot fi amândouă în mulţimea <tex> C </tex>.
Transformăm această problemă într-o instanţă de $2SAT$ astfel: faptul că nodul <tex> x </tex> aparţine mulţimii <tex> C </tex> îl reprezentăm dândui lui <tex> x </tex> valoarea <tex> 1 </tex>, iar apartenenţa mulţimii <tex> I </tex> se codifică prin valoarea <tex> 0 </tex>. Acum existenţa unei muchii <tex> (x, y) </tex> corespunde expresiei <tex> x \vee y </tex>, astfel cel puţin unul din nodurile <tex> x </tex> şi <tex> y </tex> nu va fi în mulţimea <tex> I </tex>. Dacă nu există muchia <tex> (x, y) </tex> putem scrie <tex> \sim x \vee \sim y </tex>, această expresie va fi adevărată dacă cel puţin un nod din cele două nu va fi în mulţimea <tex> C </tex>.
Această soluţie este liniară ca şi complexitate în numărul de elemente citite la intrare.

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.