ALTERNANZA, PARALLELISMO E COMPLESSITA’

[Total: 0    Average: 0/5]
Si denisce SAT come l’insieme delle formule booleane soddisfacibili, ovvero di quelle formule booleane che risultano vere per almeno un’assegnazione di valori alle variabili.
Si denisce SAT come l’insieme delle formule booleane soddisfacibili, ovvero di quelle formule booleane che risultano vere per almeno un’assegnazione di valori alle variabili. Non e noto se SAT appartiene a P (=PTIME), ovvero se esistano algoritmi per stabilire in tempo polinomiale (rispetto alla lunghezza dell’input) se una data formula booleana appartenga a SAT. E invece semplice vericare che SAT appartiene a NP (l’insieme dei problemi decisionali algoritmicamente risolubili in tempo polinomiale con una macchina non deterministica).