Funzione pseudo-booleana
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
[modifica | modifica wikitesto]Ogni funzione pseudo-booleana può essere rappresentata in maniera unica da un polinomio multilineare:[1]
Il grado della funzione corrisponde al grado del polinomio che la rappresenta.
Ottimizzazione
[modifica | modifica wikitesto]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.[2]
Submodularità
[modifica | modifica wikitesto]Le funzioni submodulari soddisfano la condizione
Sono una classe importante di funzioni pseudo-booleane, in quanto possono essere ottimizzate in tempo polinomiale.
Roof Duality
[modifica | modifica wikitesto]Roof duality è un metodo per ottenere un limite inferiore per i valori di un polinomio quadratico,[2] 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.[2]
Riduzioni
[modifica | modifica wikitesto]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.[3] Le riduzioni non sono uniche, e differenti riduzioni possono produrre risultati diversi nel processo di ottimizzazione.[4]
Riduzione del numero di variabili
[modifica | modifica wikitesto]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 .[5]
Note
[modifica | modifica wikitesto]Bibliografia
[modifica | modifica wikitesto]- 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.