Problemi del corso

Scegli un problema, segui l'esempio illustrato e passa al prossimo.

ClasseSolo completiSolo nelle tracce

36 problemi

Problema 10 di 36

MAX2SAT

Formula CNF con clausole di 2 letterali e un intero $K$ : si possono rendere vere almeno $K$ clausole?

NPNP-completo

Un esempio, passo dopo passo

1 / 3

Leggi soglia e clausole. Clausole: x∨y, x∨¬y, ¬x∨y, ¬x∨¬y. Obiettivo K = 3. — 1. Leggi soglia e clausole
Clausole: $x \lor y$ , $x \lor \neg y$ , $\neg x \lor y$ , $\neg x \lor \neg y$ . Obiettivo $K = 3$ .

Scorri l'immagine o usa Avanti.

Il certificato è un assegnamento. Si valuta ogni clausola e si conta quante sono vere, confrontando il risultato con $K$ . Chiedere che tutte le clausole di due letterali siano vere dà 2-SAT; chiedere che ne siano vere almeno $K$ cambia il problema e consente riduzioni da 3-SAT.

Complemento e collegamenti

Nessun complemento associato.

stesse clausole da 2 letterali, ma "almeno $K$ vere" è NP-completo

MAX2SAT è NP-completo

Domande e trappole d'esame

Due letterali non bastano a rendere facile un problema: conta anche la domanda. 2-SAT chiede che tutte le clausole siano vere, MAX2SAT che almeno $K$ lo siano.

Problemi del corso

1. Leggi soglia e clausole

2. Conta quelle vere

3. Confronta con $K$