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^n = {0,1}^n), 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^n, or (e) has a unique local maximum in B^n, 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 over B^n is reducible to a network minimum cut problem.