The complexity of central slice functions (Q1084375)

The k-slice of a Boolean function \(f(x_ 1,...,x_ n)\) is the function \(f_ k=(f\wedge T^ n_ k)\vee T^ n_{k+1}\), where \(T^ n_ k\) is the k-th threshold function. Berkowitz has shown that the nonmonotone combinational and monotone circuit complexities of any k-slice function differ by at most an additive term of O(n log\({}^ 2 n)\). In addition, the fact that \(f=\bigvee^{n}_{k=1}(E^ n_ k\wedge f_ k)\), where \(E^ n_ k=\neg T^ n_{k+1}\wedge T^ n_ k\), implies that if f is ''hard'' then some slice of f must have large monotone complexity. However, this latter result does not specify any particular slice and it is known that some (nontrivial) slices of NP-complete Boolean functions have linear complexity. In this paper three basic NP-complete monotone Boolean functions are examined: n/2-cliques, Hamiltonian circuits, and satisfiability. It is proved that the N/2-slice (called central slice) is NP-complete for each of these functions, where N is the total number of variables \((N=n(n-1)/2\) for the first two functions).