Answers are grounded in this paper and cite their sources.
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.
No takes yet. Share an insight, caveat, or question.
Ajtai et al. (1987) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: