Access Restriction

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

   Open content in new tab
Source: ACM Digital Library