[Teoria] Come si trova una riduzione polinomiale NP per il seguente problema.?
Una istanza di SAT si dice monotona se e’ in forma normale conguntiva (CNF, cio ́e ́e un AND di OR) le variabili che compaiono nella formula sono solo positive, ad esempio:
`(x1 ∨x2 ∨x3)∧(x2 ∨x3 ∨x5)∧(x1 ∨x3 ∨x4)`
Il problema di decisione Monotone SAT e’ definito come segue:
Input: una formula booleana `F ` in CNF monotona ed un intero` k`.
Question: e, possibile soddisfare F con un assegnamento che abbia al piu ́ k variabili vere?
`(x1 ∨x2 ∨x3)∧(x2 ∨x3 ∨x5)∧(x1 ∨x3 ∨x4)`
Il problema di decisione Monotone SAT e’ definito come segue:
Input: una formula booleana `F ` in CNF monotona ed un intero` k`.
Question: e, possibile soddisfare F con un assegnamento che abbia al piu ́ k variabili vere?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo