Miklos Ajtai, James Aspnes, et al.
Journal of Algorithms
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. © 1987, ACM. All rights reserved.
Miklos Ajtai, James Aspnes, et al.
Journal of Algorithms
Barry K. Rosen
SWAT 1972
Salvatore Certo, Anh Pham, et al.
Quantum Machine Intelligence
Vladimir Yanovski, Israel A. Wagner, et al.
Ann. Math. Artif. Intell.