Monotone versus positiveMonotone versus positive

Access Restriction
Subscribed

 Author Ajtai, Miklos ♦ Gurevich, Yuri Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1987 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract In connection with the least fixed point operator the following question was raised: Suppose that a first-order formula $\textit{P}(\textit{P})$ is (semantically) monotone in a predicate symbol $\textit{P}$ on finite structures. Is $\textit{P}(\textit{P})$ necessarily equivalent on finite structures to a first-order formula with only positive occurrences of $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1987-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 34 Issue Number 4 Page Count 12 Starting Page 1004 Ending Page 1015

Open content in new tab

Source: ACM Digital Library