Una funzione pseudo-booleana è una funzione nella forma

,

dove è un dominio booleano e n è un intero non negativo che rappresenta l'arietà della funzione. Una funzione booleana è un caso speciale di funzione pseudo-booleana a valori booleani.

Rappresentazione

Ogni funzione pseudo-booleana può essere rappresentata in maniera unica da un polinomio multilineare:

Il grado della funzione corrisponde al grado del polinomio che la rappresenta.

Ottimizzazione

L'ottimizzazione di una funzione pseudo-booleana nel caso generale è un problema NP-hard. Questo può essere dimostrato facilmente, formulando il problema del taglio massimo come massimizzazione di una funzione pseudo-booleana.

Submodularità

Le funzioni submodulari soddisfano la condizione

Sono una classe importante di funzioni pseudo-booleane, in quanto possono essere ottimizzate in tempo polinomiale.

Roof Duality

Roof duality è un metodo per ottenere un limite inferiore per i valori di un polinomio quadratico, e può essere usato per determinare un assegnamento ottimale parziale delle variabili. È un metodo piuttosto generale, e diversi metodi di ottimizzazione si sono rivelati essere equivalenti ad esso.

Riduzioni

Le funzioni di grado superiore a 2 possono sempre essere ridotte ad una funzione quadratica equivalente dal punto di vista del problema di ottimizzazione, tramite l'aggiunta di variabili ausiliarie. Le riduzioni non sono uniche, e differenti riduzioni possono produrre risultati diversi nel processo di ottimizzazione.

Riduzione del numero di variabili

Data una funzione pseudo-booleana a coefficienti interi, e un intero , il problema di determinare se è minore o uguale a è NP-completo. In tempo polinomiale è possibile alternativamente risolvere o ridurre il numero delle variabili a . Dato il grado del polinomio associato a , in tempo polinomiale è possibile alternativamente risolvere o ridurre il numero di variabili a .

Note Boros and Hammer, 2002

Ishikawa, 2011

Kahl and Strandmark, 2011

Crowston et al., 2011

Bibliografia

Voci correlate Funzione booleana

Categoria:Ottimizzazione