article

Free access

Monotone versus positive

Authors:

Miklos Ajtai,

Yuri GurevichAuthors Info & Claims

Journal of the ACM (JACM), Volume 34, Issue 4

Pages 1004 - 1015

https://doi.org/10.1145/31846.31852

Published: 01 October 1987 Publication History

PDF eReader

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.

References

[1]

AJTAi, M. ~-formulae on finite structures. Ann. Pure Appl. Logic 24 (1983), 1--48.

Google Scholar

[2]

BOPPANA, R. H. Threshold functions and bounded depth monotone circuits. In Proceedings of the 16th ACM Symposium on Theory of Computing (Washington, D.C., Apr. 30-May 2). ACM, New York, 1984, pp. 475--479.

Crossref

Google Scholar

[3]

CHANDRA, A. K., AND HAREL, D. Structure and complexity of relational queries. J. Comput. Syst. Sci. 25 (1980), 156-178.

Google Scholar

[4]

CHANG, C. C., AND K~ISLER, H.J. Model Theory. North-Holland, New York, 1977.

Google Scholar

[5]

FURST, M., SAXE, J., AND SXPSER, M. Parity, circuits, and the polynomial time hierarchy. Math. Syst. Theory 17 (1984), 13-27.

Google Scholar

[6]

GUREVlCH, Y. Toward logic tailored for computational complexity. In Computation and Proof Theory, M. M. Richter, E. B6rger, W. Oberschelp, B. Schinzel, and W. Thomas, Eds. Lecture Notes in Mathematics, vol. 1104. Springer-Verlag, New York, 1984, pp. 175-216.

Google Scholar

[7]

GUREVlCI4, Y. Logic and the challenge of computer science. In Current Trends in Theoretical Computer Science, E. B6rger, Ed. Computer Science Press, Rockville, Md., 1987, pp. 1-57.

Google Scholar

[8]

GUR~VlCH, Y., AND SHELAH, S. Fixed point extensions of first order logic. In Proceedings of the 26th IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1985, pp. 346-353.

Google Scholar

[9]

HARDY, (~. H., AND WRIGHT, E.M. An Introduction to the Theory of Numbers. Clarendon Press, Oxford, England, 1971.

Google Scholar

[10]

KLEENE, S.C. Introduction to Metamathematics. Van Nostrand, New York, 1952.

Google Scholar

[11]

LYNDON, R.C. An interpolation theorem in the predicate calculus. Pacific J. Math. 9 (1959), 155-164.

Google Scholar

[12]

SIPSER, M. Borel sets and circuit complexity. In Proceedings of the 15th ACM Symposium on Theory of Computing. ACM New York, 1983, pp. 61-69.

Crossref

Google Scholar

Cited By

View all

Cavalar BOliveira I(2023)Constant-Depth Circuits vs. Monotone CircuitsProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.29(1-37)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.29
Gurevich Y(2023)The umbilical cord of finite model theoryJournal of Logic and Computation10.1093/logcom/exad055Online publication date: 1-Sep-2023
https://doi.org/10.1093/logcom/exad055
Das ADelkos A(2022)Proof Complexity of Monotone Branching ProgramsRevolutions and Revelations in Computability10.1007/978-3-031-08740-0_7(74-87)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-08740-0_7
Show More Cited By

Index Terms

Monotone versus positive
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Logic

Recommendations

Positive Monotone Modal Logic
Abstract
Positive monotone modal logic is the negation- and implication-free fragment of monotone modal logic, i.e., the fragment with connectives [inline-graphic not available: see fulltext] and [inline-graphic not available: see fulltext]. We axiomatise ... $^{}$
From positive and intuitionistic bounded arithmetic to monotone proof complexity
LICS '16: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science

We study versions of second-order bounded arithmetic where induction and comprehension formulae are positive or where the underlying logic is intuitionistic, examining their relationships to monotone and deep inference proof systems for propositional ...
Extending Downward Collapse from 1-versus-2 Queries to m-versus-m + 1 Queries

The top part of Figure 1.1 shows some classes from the (truth-table) bounded-query and boolean hierarchies. It is well known that if either of these hierarchies collapses at a given level, then all higher levels of that hierarchy collapse to that same ...

Reviews

Reviewer: Thomas B. Hilburn

In [1], Yuri Gurevich discusses the achievements of mathematical logic and states that “logic grows more relevant to computer science than any other part of mathematics.” He goes on to argue that applications in computer science require new formalizations that are related to the “finiteness” and the “dynamic” characters of the computer. The authors of this paper carry on in this spirit. The main result established is that if a first order formula &fgr;( P) is monotone in a predicate symbol P over finite structures it is not necessarily positive in P. (A formula &fgr;( P) is said to be monotone in P if P ? Q logically implies &fgr;( P) ? &fgr;( Q); a formula is said to be positive if it is equivalent to a formula without any negation signs.) The authors construct a monotone formula in P that is not positive in P. This example is used to establish a related result about monotone Boolean circuits and positive Boolean circuits, which provides a basis for a study of the lower bounds on the complexity of Boolean circuits. With the exception of a few bothersome typographical errors the paper is well written, and the proof of the main theorem is impressive. However, its contents will only be accessible to someone with a knowledge of first order logic and some familiarity with the literature in the field.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1987

Published in JACM Volume 34, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

76
Total Citations
View Citations
549
Total Downloads

Downloads (Last 12 months)63
Downloads (Last 6 weeks)7

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Cavalar BOliveira I(2023)Constant-Depth Circuits vs. Monotone CircuitsProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.29(1-37)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.29
Gurevich Y(2023)The umbilical cord of finite model theoryJournal of Logic and Computation10.1093/logcom/exad055Online publication date: 1-Sep-2023
https://doi.org/10.1093/logcom/exad055
Das ADelkos A(2022)Proof Complexity of Monotone Branching ProgramsRevolutions and Revelations in Computability10.1007/978-3-031-08740-0_7(74-87)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-08740-0_7
Murwanashyaka J(2022)Hilbert’s Tenth Problem for Term Algebras with a Substitution OperatorRevolutions and Revelations in Computability10.1007/978-3-031-08740-0_17(196-207)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-08740-0_17
Chattopadhyay ADatta RMukhopadhyay PKhuller SVassilevska Williams V(2021)Lower bounds for monotone arithmetic circuits via communication complexityProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451069(786-799)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451069
Kuperberg DGorla D(2021)Positive first-order logic on wordsProceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science10.1109/LICS52264.2021.9470602(1-13)Online publication date: 29-Jun-2021
https://dl.acm.org/doi/10.1109/LICS52264.2021.9470602
Ikenmeyer CKomarath BLenzen CLysikov VMokhov ASreenivasaiah K(2019)On the Complexity of Hazard-free CircuitsJournal of the ACM10.1145/332012366:4(1-20)Online publication date: 23-Aug-2019
https://dl.acm.org/doi/10.1145/3320123
Surinx DVan den Bussche J(2019)A Monotone Preservation Result for Boolean Queries Expressed as a Containment of Conjunctive QueriesInformation Processing Letters10.1016/j.ipl.2019.06.001Online publication date: Jun-2019
https://doi.org/10.1016/j.ipl.2019.06.001
Ikenmeyer CKomarath BLenzen CLysikov VMokhov ASreenivasaiah KDiakonikolas IKempe DHenzinger M(2018)On the complexity of hazard-free circuitsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188912(878-889)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188912
Surinx DVan den Bussche JVan Gucht D(2018)A Framework for Comparing Query Languages in Their Ability to Express Boolean QueriesFoundations of Information and Knowledge Systems10.1007/978-3-319-90050-6_20(360-378)Online publication date: 18-Apr-2018
https://doi.org/10.1007/978-3-319-90050-6_20
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Positive Monotone Modal Logic

From positive and intuitionistic bounded arithmetic to monotone proof complexity

Extending Downward Collapse from 1-versus-2 Queries to m-versus-m + 1 Queries

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations