Visualizza wikitesto di Funzione pseudo-booleana

Una '''funzione pseudo-booleana''' è una [[funzione (matematica)|funzione]] nella forma

:<math>f:\mathbb{B}^n \rightarrow \mathbb{R}</math>,

dove <math>\mathbb{B}</math> è 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:<ref name="note2"/>

:<math>f(x) = a + \sum_i a_ix_i + \sum_{i<j}a_{ij}x_ix_j + \sum_{i<j<k}a_{ijk}x_ix_jx_k + \ldots </math>

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.<ref name="boroshammer" />

=== Submodularità ===

Le funzioni submodulari soddisfano la condizione

:<math> f(x) + f(y) \ge  f(x \wedge y) + f(x \vee y), \quad \forall x, y\in \mathbb{B}^n . </math>

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,<ref name="boroshammer"/> 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.<ref name="boroshammer" />

=== 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.<ref name="ishikawa2011"/> Le riduzioni non sono uniche, e differenti riduzioni possono produrre risultati diversi nel processo di ottimizzazione.<ref name="kahlstrandmark"/>

=== Riduzione del numero di variabili ===

Data una funzione pseudo-booleana <math>\textstyle f(x)= \sum_{I\subseteq [n]} w_i \prod_{i\in I} x_i </math> a coefficienti interi, e un intero <math>k</math>, il problema <math>P</math> di determinare se <math>f(x)</math> è minore o uguale a <math>k</math> è [[NP-completo]]. In tempo polinomiale è possibile alternativamente risolvere <math>P</math> o ridurre il numero delle variabili a <math> O(k^2\log k) </math>. Dato il grado <math>r</math> del polinomio associato a <math>f</math>, in tempo polinomiale è possibile alternativamente risolvere <math>P</math> o ridurre il numero di variabili a <math> r(k-1) </math>.<ref name="crow"/>

== Note ==
<references>

<ref name="note2">
{{Cita libro|titolo= Boolean Methods in Operations Research and Related Areas
 |cognome= Hammer
 |nome= Peter L.
 |editore= Springer
 |anno= 1968
 | isbn = 978-3-642-85825-3
 |città= 
 |cognome2= Rudeanu
 |nome2= Sergiu
}}</ref>

<ref name="boroshammer">Boros and Hammer, 2002</ref>

<ref name="ishikawa2011">Ishikawa, 2011</ref>

<ref name="kahlstrandmark">Kahl and Strandmark, 2011</ref>

<ref name="crow">Crowston et al., 2011</ref>

</references>

== Bibliografia ==
* {{Cita pubblicazione|cognome=Boros|autore2=Hammer |titolo=Pseudo-Boolean Optimization|rivista=Discrete Applied Mathematics|anno=2002|volume=123|doi=10.1016/S0166-218X(01)00341-9}}
* {{Cita pubblicazione|cognome=Crowston |autore2=Fellows, Gutin |autore3=Jones, Rosamond |autore4=Thomasse, Yeo|titolo=Simultaneously Satisfying Linear Equations Over GF(2): MaxLin2 and Max-r-Lin2 Parameterized Above Average.|rivista=Proc. of FSTTCS 2011|anno=2011|arxiv=1104.1135|bibcode=2011arXiv1104.1135C}}
* {{Cita pubblicazione|cognome=Ishikawa|titolo=Transformation of general binary MRF minimization to the first order case|rivista=IEEE Transactions on Pattern Analysis and Machine Intelligence|anno=2011|volume=33|numero=6|pp=1234-1249|doi=10.1109/tpami.2010.91}}
* {{Cita pubblicazione|cognome=Rother|autore2=Kolmogorov|autore3=Lempitsky|autore4=Szummer|titolo=Optimizing Binary MRFs via Extended Roof Duality|rivista=International Conference on Computer Vision and Pattern Recognition|anno=2007|url=http://research.microsoft.com/pubs/67978/cvpr07-QPBOpi.pdf}}
* {{Cita pubblicazione|cognome=Kahl|autore2=Strandmark |titolo=Generalized Roof Duality for Pseudo-Boolean Optimization|rivista=International Conference on Computer Vision |anno=2011|url=http://www.maths.lth.se/vision/publdb/reports/pdf/kahl-strandmark-iccv-11.pdf}}
* {{Cita pubblicazione|cognome=O'Donnell|nome=Ryan|titolo=Some topics in analysis of Boolean functions|rivista=Electronic Colloquium on Computational Complexity
|anno=2008|url=http://www.eccc.uni-trier.de/eccc-reports/2008/TR08-055/}}

== Voci correlate ==
*[[Funzione booleana]]
{{portale|matematica}}

[[Categoria:Ottimizzazione]]