Article

Free access

Two new upper bounds for SAT

Author:

Edward A. HirschAuthors Info & Claims

SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms

Pages 521 - 530

Published: 01 January 1998 Publication History

PDF eReader

References

[1]

E. Dantsin, Tautology proof systems based on the splitting method, Leningrad Division of Steklov Institute of Mathematics (LOMI), PhD Dissertation, Leningrad, 1982 (in Russian).

Google Scholar

[2]

E. Dantsin and L. O. Fuentes and V. Kreinovich, Less than 2~ satisfiability algorithm extended to the case when almost all clauses are short, Computer Science Department, University ot' Texas at E1 Paso, UTEP- CS-91-5, 1991.

Google Scholar

[3]

E. Ya. Dantsin, V. Ya. Kreinovich, Exponential upper bounds for the satisfiability problem, Proc. of the IX USSR conf. on math. logic, Leningrad, 1988 (in Russian).

Google Scholar

[4]

M. Davis, G. Logemann, D. Loveland, A machine program for theorem-proving, Comm. ACM, vol. 5, 1962, pp. 394-397.

Digital Library

Google Scholar

[5]

M. Davis, H. Putnam, A computing procedure for quantification theory, J. ACM, vol. 7, 1960, pp. 201-215.

Digital Library

Google Scholar

[6]

E. A. Hirsch, Separating the signs in the satisfiability problem, Zap. nauchn, semin. POMI, vol. 241, 1997 (in Russian). To appear. English translation of this collection is to appear in 1999.

Google Scholar

[7]

O. Kullmann, Worst-case analysis, 3-SAT decision and lower bounds: approaches for improved SAT algorithms, DIMACS Proc. SAT Workshop 1996, AMS, 1996.

Google Scholar

[8]

O. Kullmarm, H. Luckhardt, Deciding propositional tautologies: Algorithms and their complexity, submitted to Information and Computation, 1997.

Google Scholar

[9]

H. Luckhardt, Obere Komplexith'tsschranken fiir TA UT-Entscheidungen, Proc. Frege Conference 1984, Schwerine, Akademie-Verlag Berline, pp. 331-337.

Google Scholar

[10]

B. Monien, E. Speckenmeyer, 3-satisfiability is testable in O(1.62r) steps, Bericht Nr. 3/1979, Reihe Theoretische Informatik, Universit/it-Gesamthochschule- Paderborn.

Google Scholar

[11]

B. Monien, E. Speckenmeyer, Upper bounds for covering problems, Bericht Nr. 7/1980, Reihe Theoretische Informatik, Universit/it- Gesamthochschule-Paderborn.

Google Scholar

[12]

B. Monien, E. Speckenmeyer, Solving satisfiability in less then 2n steps, Discrete Applied Mathematics, vol. 10, 1985, pp. 287-295.

Google Scholar

[13]

J. A. Robinson, Generalized resolution principle, Machine Intelligence, vol. 3, 1968, pp. 77-94.

Google Scholar

[14]

I. Schiermeyer, Solving 3-satisfiability in less than 1.579" steps, LNCS 702, 1993, pp. 379-394.

Digital Library

Google Scholar

[15]

I. Schiermeyer, Pure literal look ahead: An 0(1.497") 3- Satisfiability algorithm, Workshop on the Satisfiability Problem, Technical Report, Siena, April, 29- May, 3, 1996; University KSln, Report No. 96-230.

Google Scholar

Cited By

View all

Williams V(2018)Some Open Problems in Fine-Grained ComplexityACM SIGACT News10.1145/3300150.330015849:4(29-35)Online publication date: 15-Dec-2018
https://dl.acm.org/doi/10.1145/3300150.3300158
Backurs ARoditty LSegal GWilliams VWein NDiakonikolas IKempe DHenzinger M(2018)Towards tight approximation bounds for graph diameter and eccentricitiesProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188950(267-280)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188950
Abboud AVassilevska Williams VYu HServedio RRubinfeld R(2015)Matching Triangles and Basing Hardness on an Extremely Popular ConjectureProceedings of the forty-seventh annual ACM symposium on Theory of Computing10.1145/2746539.2746594(41-50)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2746539.2746594
Show More Cited By

Index Terms

Two new upper bounds for SAT
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation

Recommendations

New Worst-Case Upper Bounds for SAT

In 1980 Monien and Speckenmeyer proved that satisfiability of a propositional formula consisting of i>K clauses (of arbitrary length) can be checked in time of the order 2^{i>K / 3}. Recently Kullmann and Luckhardt proved the worst-case upper bound 2^...
A new approach to proving upper bounds for MAX-2-SAT
SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm

In this paper we present a new approach to proving upper bounds for the maximum 2-satisfiability problem (MAX-2-SAT). We present a new 2^K/5.5-time algorithm for MAX-2-SAT, where K is the number of clauses in an input formula. We also obtain a 2^N/6 bound,...
New Upper Bounds for Maximum Satisfiability

The (unweighted) Maximum Satisfiability problem (MaxSat) is: Given a Boolean formula in conjunctive normal form, find a truth assignment that satisfies the largest number of clauses. This paper describes exact algorithms that provide new upper bounds ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms

January 1998

704 pages

ISBN:0898714109

Chairman:
Howard Karloff

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 1998

Check for updates

Qualifiers

Article

Conference

SODA98

Sponsor:

SIGACT
SIAM

SODA98: 1998 Conference on Discrete Algorithms

January 25 - 27, 1998

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
248
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)2

Reflects downloads up to 09 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Williams V(2018)Some Open Problems in Fine-Grained ComplexityACM SIGACT News10.1145/3300150.330015849:4(29-35)Online publication date: 15-Dec-2018
https://dl.acm.org/doi/10.1145/3300150.3300158
Backurs ARoditty LSegal GWilliams VWein NDiakonikolas IKempe DHenzinger M(2018)Towards tight approximation bounds for graph diameter and eccentricitiesProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188950(267-280)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188950
Abboud AVassilevska Williams VYu HServedio RRubinfeld R(2015)Matching Triangles and Basing Hardness on an Extremely Popular ConjectureProceedings of the forty-seventh annual ACM symposium on Theory of Computing10.1145/2746539.2746594(41-50)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2746539.2746594
Roditty LVassilevska Williams VBoneh DRoughgarden TFeigenbaum J(2013)Fast approximation algorithms for the diameter and radius of sparse graphsProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488673(515-524)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488673
Drori LPeleg D(2002)Faster exact solutions for some NP-hard problemsTheoretical Computer Science10.1016/S0304-3975(01)00257-2287:2(473-499)Online publication date: 28-Sep-2002
https://dl.acm.org/doi/10.1016/S0304-3975%2801%2900257-2
Eppstein DKosaraju S(2001)Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfactionProceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms10.5555/365411.365471(329-337)Online publication date: 9-Jan-2001
https://dl.acm.org/doi/10.5555/365411.365471
Hirsch E(2000)New Worst-Case Upper Bounds for SATJournal of Automated Reasoning10.1023/A:100634092010424:4(397-420)Online publication date: 1-May-2000
https://dl.acm.org/doi/10.1023/A%3A1006340920104
Hirsch E(2000)SAT Local Search AlgorithmsJournal of Automated Reasoning10.1023/A:100631852118524:1-2(127-143)Online publication date: 1-Feb-2000
https://dl.acm.org/doi/10.1023/A%3A1006318521185

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

New Worst-Case Upper Bounds for SAT

A new approach to proving upper bounds for MAX-2-SAT

New Upper Bounds for Maximum Satisfiability