Recognition problems for special classes of polynomials in 0-1 variables (Q1121786): Difference between revisions

The following decision problem P is considered. Given a pseudo-Boolean function f in polynomial form and a class C of pseudo-Boolean functions, is f not in C? For the classes of monotonic, supermodular, threshold, completely unimodular, and unimax functions it is shown that P is NP- complete. In each case there is a reduction from the partition problem to P. For the class of unimodular functions a polynomial algorithm is presented which solves P.