Monotone versus positive
- 1 October 1987
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 34 (4) , 1004-1015
- https://doi.org/10.1145/31846.31852
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.Keywords
This publication has 4 references indexed in Scilit:
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- Toward logic tailored for computational complexityLecture Notes in Mathematics, 1984
- ∑11-Formulae on finite structuresAnnals of Pure and Applied Logic, 1983
- An interpolation theorem in the predicate calculusPacific Journal of Mathematics, 1959