Monotone versus positive

Authors:
Open Access
Publisher website
Google Scholar
Abstract
In connection with the least fixed point operator the following question was raised: Suppose that a first-order formula P ( P ) is (semantically) monotone in a predicate symbol P on finite structures. Is P ( P ) necessarily equivalent on finite structures to a first-order formula with only positive occurrences of P ? In this paper, this question is answered negatively. Moreover, the counterexample naturally gives a uniform sequence of constant-depth, polynomial-size, monotone Boolean circuits that is not equivalent to any (however nonuniform) sequence of constant-depth, polynomial-size, positive Boolean circuits.