Supponendo che P = NP - Trova un algoritmo ottimale per 3sat
-
05-11-2019 - |
Domanda
Supponiamo che P = NP quindi abbiamo algoritmi di ricerca e decisioni per 3SAT al momento polinomiale.
Puoi aiutarmi a trovare un algoritmo ottimale per ottimizzare 3Sat, cioè: per trovare il numero massimo di clausole in $ varphi $ che possono essere soddisfatte.
Grazie!
Ps
Puoi supporre che tu abbia algoritmi di ricerca e decisioni per 3sat al momento del polinomio, quindi puoi usarli ...
Nessuna soluzione corretta
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange