«

»

Mag 13

SAT

Mi sono per caso imbattuto in una sigla che nasconde un problema formidabile dall’aspetto innocuo: data una funzione booleana (guadagno = lavoro o gioco a Win For Life) determinare se esiste una combinazione (vero, falso) delle variabili che rende vera la funzione.

E’ questo il problema della soddisfacibilità (SATisfiability) di una espressione. Problema arduo più di quanto avessi immaginato: è addirittura un problema NP-completo, come il problema del commesso viaggiatore.

Questo è il sito del Journal On Satisfability Boolean Modeling And Computation in cui è possibile farsi un’idea.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

Puoi usare i seguenti tag ed attributi HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>