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 hypercube B“={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 of B“, or (e) has a unique local maximum in B”, is shown to be NP-hard. A polynomial-time recognition algorithm is presented for unimodular functions, previously introduced by Hasen and Simeone as a class of functions whose maximization over B“ is reducible to a network minimum cut problem.