Funzione pseudo-booleana

Una funzione pseudo-booleana è una funzione nella forma

$f:{𝔹}^n\to ℝ$,

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:

$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+\dots$

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)\ge f(x\wedge y)+f(x\vee y),\mathrm{\forall }x,y\in {𝔹}^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 $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)$.

Bibliografia

• Template:Cita pubblicazione
• Template:Cita pubblicazione
• Template:Cita pubblicazione
• Template:Cita pubblicazione
• Template:Cita pubblicazione
• Template:Cita pubblicazione

Voci correlate

• Funzione booleana