Recognition problems for special classes of polynomials in 0–1 variables

This paper investigates the complexity of various recognition problems for pseudo-Boolean functions (i.e., real-valued functions defined on the unit hypercubeB ⁿ = {0, 1} ⁿ ), when such functions are represented as multilinear polynomials in their variables. Determining whether a pseudo-Boolean function (a) is monotonic, or (b) is supermodular, or (c) is threshold, or (d) has a unique local maximum in each face ofB ⁿ , or (e) has a unique local maximum inB ⁿ , is shown to be NP-hard. A polynomial-time recognition algorithm is presented for unimodular functions, previously introduced by Hansen and Simeone as a class of functions whose maximization overB ⁿ is reducible to a network minimum cut problem.