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)$.

Bibliografia

• Boros e Hammer, Pseudo-Boolean Optimization, in Discrete Applied Mathematics, vol. 123, 2002, DOI:10.1016/S0166-218X(01)00341-9.
• Crowston, Fellows, Gutin, Jones, Rosamond e Thomasse, Yeo, Simultaneously Satisfying Linear Equations Over GF(2): MaxLin2 and Max-r-Lin2 Parameterized Above Average., in Proc. of FSTTCS 2011, 2011, Bibcode:2011arXiv1104.1135C, arXiv:1104.1135.
• Ishikawa, Transformation of general binary MRF minimization to the first order case, in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, n. 6, 2011, pp. 1234–1249, DOI:10.1109/tpami.2010.91.
• Rother, Kolmogorov, Lempitsky e Szummer, Optimizing Binary MRFs via Extended Roof Duality (PDF), in International Conference on Computer Vision and Pattern Recognition, 2007.
• Kahl e Strandmark, Generalized Roof Duality for Pseudo-Boolean Optimization (PDF), in International Conference on Computer Vision, 2011.
• Ryan O'Donnell, Some topics in analysis of Boolean functions, in Electronic Colloquium on Computational Complexity, 2008.

Voci correlate

• Funzione booleana