Recognition problems for special classes of polynomials in 0-1 variables (Q1121786)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Recognition problems for special classes of polynomials in 0-1 variables
scientific article

    Statements

    Recognition problems for special classes of polynomials in 0-1 variables (English)
    0 references
    0 references
    1989
    0 references
    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.
    0 references
    0 references
    0 references
    pseudo-Boolean function
    0 references
    unimax functions
    0 references
    NP-complete
    0 references
    unimodular functions
    0 references
    polynomial algorithm
    0 references
    0 references