Article

Free access

Using the Groebner basis algorithm to find proofs of unsatisfiability

Authors:

Matthew Clegg,

Jeffery Edmonds,

Russell ImpagliazzoAuthors Info & Claims

STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing

Pages 174 - 183

https://doi.org/10.1145/237814.237860

Published: 01 July 1996 Publication History

PDF eReader

References

[1]

P. Beame, R. Impagliazzo, J. Krajicek, T. Pitassi, and P. Pudlak Lower bounds on Hilbert's Nullstellensatz and propositional proofs in 35th Annual Symposium on Foundations o/Computer Science, pages 794-806, Santa Fe, November 1994.]]

Google Scholar

[2]

P. Beame, S. Cook,J. Edmonds, R. Impagliazzo, T. Pitassi, The Relativized Complexity of Search Problems, Proc. of 27'th STOC, 1995, pp. 303-314.]]

Digital Library

Google Scholar

[3]

B. Buchberger, Ein Algorithmus zum Auftinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, (An algorithm for finding a basis for the residue class ring of a zerodimensional polynomial ideal). Doctoral Dissertation Math. Inst. University of Innsbruck, Austria.]]

Google Scholar

[4]

B. Buchberger, A criterion for detecting unneccessary reductions in the construction of GrSbner bases. In: Ng, E.W. (ed.), EUROSAM '79, An International Symposium on Symbolic and Algebraic Manipulation, Springer LNCS 72, 3-21.]]

Digital Library

Google Scholar

[5]

S. Buss and T. Pitassi, to appear in ll~th Computational Complexity, 1996.]]

Google Scholar

[6]

M. Clegg and R. Impagliazzo. "Homogenization and Nullstellensatz Degrees". In preparation.]]

Google Scholar

[7]

M. Clegg and N. Wallach, "Groebner: A Commutative Algebra Package for Distributed Networks of Workstations". In preparation.]]

Google Scholar

[8]

D. Cox, J. Little, D. O'Shea, Ideals, Varieties and Algorithms, Springer, 1992.]]

Digital Library

Google Scholar

[9]

K. Iwana, and E. Miyano. Intractability of Read- Once Resolution, 10'th Structures, 1995. pp. 29-36.]]

Digital Library

Google Scholar

[10]

S. Kirkpatrick and B. Selman, Critical Behavior in the Satisfiability of Random Boolean Expressions. Science, Vol. 264, May 1994, 1297-1301.]]

Crossref

Google Scholar

[11]

L. Lovasz, On the Shannon Capacity of a graph, Transactions on Information Theory, vol. 25, No. 1, January, 1979]]

Crossref

Google Scholar

[12]

T. Pitassi, personal communication, 1995.]]

Google Scholar

[13]

A. Razbarov and S. Rudich, Natural Proofs, Proc. of 26th STOC, 1994, pp. 204-213.]]

Digital Library

Google Scholar

[14]

B. Selman, personal communication, 1995.]]

Google Scholar

Cited By

View all

Torán JWörz F(2024)Cutting Planes Width and the Complexity of Graph Isomorphism RefutationsACM Transactions on Computational Logic10.1145/367712125:4(1-25)Online publication date: 18-Jul-2024
https://dl.acm.org/doi/10.1145/3677121
Mikša MNordström J(2024)A Generalized Method for Proving Polynomial Calculus Degree Lower BoundsJournal of the ACM10.1145/367566871:6(1-43)Online publication date: 4-Jul-2024
https://dl.acm.org/doi/10.1145/3675668
Gryaznov SOvcharov SRiazanov A(2024)Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and SpaceACM Transactions on Computation Theory10.1145/367541516:3(1-15)Online publication date: 11-Jul-2024
https://dl.acm.org/doi/10.1145/3675415
Show More Cited By

Index Terms

Using the Groebner basis algorithm to find proofs of unsatisfiability
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

A new incremental algorithm for computing Groebner bases
ISSAC '10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation

In this paper, we present a new algorithm for computing Gröbner bases. Our algorithm is incremental in the same fashion as F5 and F5C. At a typical step, one is given a Gröbner basis G for an ideal I and any polynomial g, and it is desired to compute a ...
New algorithms for computing groebner bases
Groebner Basis Under Composition I

Composition is the operation of replacing variables in a polynomial with other polynomials. The main question of this paper is:When does composition commute with Groebner basis computation__ __We prove that this happens iff the composition is `...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing

July 1996

661 pages

ISBN:0897917855

DOI:10.1145/237814

Chairman:
Gary L. Miller

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC96

Sponsor:

SIGACT

STOC96: ACM Symposium on Theory of Computing

May 22 - 24, 1996

Pennsylvania, Philadelphia, USA

Acceptance Rates

STOC '96 Paper Acceptance Rate 74 of 201 submissions, 37%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

211
Total Citations
View Citations
1,485
Total Downloads

Downloads (Last 12 months)225
Downloads (Last 6 weeks)26

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Torán JWörz F(2024)Cutting Planes Width and the Complexity of Graph Isomorphism RefutationsACM Transactions on Computational Logic10.1145/367712125:4(1-25)Online publication date: 18-Jul-2024
https://dl.acm.org/doi/10.1145/3677121
Mikša MNordström J(2024)A Generalized Method for Proving Polynomial Calculus Degree Lower BoundsJournal of the ACM10.1145/367566871:6(1-43)Online publication date: 4-Jul-2024
https://dl.acm.org/doi/10.1145/3675668
Gryaznov SOvcharov SRiazanov A(2024)Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and SpaceACM Transactions on Computation Theory10.1145/367541516:3(1-15)Online publication date: 11-Jul-2024
https://dl.acm.org/doi/10.1145/3675415
Göös MHollender AJain SMaystre GPires WRobere RTao R(2024)Separations in Proof Complexity and TFNPJournal of the ACM10.1145/366375871:4(1-45)Online publication date: 9-May-2024
https://dl.acm.org/doi/10.1145/3663758
Bonacina IBonet MLevy J(2024)Polynomial Calculus for OptimizationArtificial Intelligence10.1016/j.artint.2024.104208(104208)Online publication date: Aug-2024
https://doi.org/10.1016/j.artint.2024.104208
Part FThapen NTzameret I(2024)First-Order Reasoning and Efficient Semi-Algebraic ProofsAnnals of Pure and Applied Logic10.1016/j.apal.2024.103496(103496)Online publication date: Jul-2024
https://doi.org/10.1016/j.apal.2024.103496
Impagliazzo RMouli SPitassi T(2023)Lower Bounds for Polynomial Calculus with Extension Variables over Finite FieldsProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.7(1-24)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.7
Galesi NGrochow JPitassi TShe A(2023)On the Algebraic Proof Complexity of Tensor IsomorphismProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.4(1-40)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.4
史美(2023)Authenticator for Verification Results of Multiplier Circuits Based on Variable OrderingComputer Science and Application10.12677/CSA.2023.131019613:10(1980-1987)Online publication date: 2023
https://doi.org/10.12677/CSA.2023.1310196
Conneryd JDe Rezende SNordström JPang SRisse K(2023)Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00007(1-11)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00007
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

A new incremental algorithm for computing Groebner bases

New algorithms for computing groebner bases

Groebner Basis Under Composition I