L'ottimizzazione di funzioni pseudo-booleane di ordine superiore, ovvero contenenti termini dipendenti da tre o più variabili, è in generale un problema difficile. È sempre possibile ridurre in tempo polinomiale una funzione di ordine superiore a una funzione quadratica, equivalente rispetto al problema di ottimizzazione,in(problema temponoto polinomialecome ''higher-order [[cricca (teoria dei grafi)|clique]] reduction'', HOCR), e il risultato di tale riduzione può essere ottimizzato con QPBO. Metodi generali per la riduzione di funzioni arbitrarie sono basati su opportune tecniche di sostituzione di sotto-espressioni e in generale richiedono l'introduzione di variabili ausiliarie.<ref name="fix" /> In pratica, per la maggior parte dei termini di ordine superiore è possibile calcolare in maniera esatta una riduzione senza aggiunta di variabili ausiliarie, risultando in un problema di ottimizzazione più semplice; per i restanti termini irriducibili è possibile calcolare una riduzione esatta con metodi più generali, aggiungendo variabili ausiliarie, oppure eseguendo una riduzione approssimata senza aggiungere nuove variabili.<ref name="elc" />
== Note ==
Riga 63:
== Collegamenti esterni ==
* [http://pub.ist.ac.at/~vnk/software.html#qpbo Implementazione di QPBO in C++ di QPBO], distribuita sotto [[GNU General Public License|licenza GPL]], a cura di Vladimir Kolmogorov.
* [http://www.f.waseda.jp/hfs/software.html Implementazione in C++ di HOCR], distribuita sotto [[licenza MIT]], a cura di Hiroshi Ishikawa.
