Funzione pseudo-booleana
# Funzione pseudo-booleana

Una funzione pseudo-booleana è una funzione nella forma

    $f:\mathbb {B} ^{n}\rightarrow \mathbb {R}$,

dove $\mathbb {B}$ è 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:

    $f(x)=a+\sum _{i}a_{i}x_{i}+\sum _{i<j}a_{ij}x_{i}x_{j}+\sum _{i<j<k}a_{ijk}x_{i}x_{j}x_{k}+\ldots$

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

    $f(x)+f(y)\geq f(x\wedge y)+f(x\vee y),\quad \forall x,y\in \mathbb {B} ^{n}.$

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 $\textstyle f(x)=\sum _{I\subseteq [n]}w_{i}\prod _{i\in I}x_{i}$ a coefficienti interi, e un intero $k$, il problema $P$ di determinare se $f(x)$ è minore o uguale a $k$ è NP-completo. In tempo polinomiale è possibile alternativamente risolvere $P$ o ridurre il numero delle variabili a $O(k^{2}\log k)$. Dato il grado $r$ del polinomio associato a $f$, in tempo polinomiale è possibile alternativamente risolvere $P$ o ridurre il numero di variabili a $r(k-1)$.

