# The complexity of satisfiability problems

@article{Schaefer1978TheCO, title={The complexity of satisfiability problems}, author={Thomas J. Schaefer}, journal={Proceedings of the tenth annual ACM symposium on Theory of computing}, year={1978} }

The problem of deciding whether a given propositional formula in conjunctive normal form is satisfiable has been widely studied. I t is known that, when restricted to formulas having only two literals per clause, this problem has an efficient (polynomial-time) solution. But the same problem on formulas having three literals per clause is NP-complete, and hence probably does not have any efficient solution. In this paper, we consider an infinite class of satisfiability problems which containsâ€¦Â Expand

#### Topics from this paper

#### 1,912 Citations

Complexity of Generalized Satisfiability Counting Problems

- Computer Science, Mathematics
- Inf. Comput.
- 1996

A Dichotomy Theorem is proved that if all logical relations involved in a generalized satisfiability counting problem are affine then the number of satisfying assignments of this problem can be computed in polynomial time, otherwise this function is #P-complete. Expand

The complexity of minimal satisfiability problems

- Computer Science, Mathematics
- Inf. Comput.
- 2003

A dichotomy theorem is established for the class of all MIN SAT(S)-problems, where S is a finite set of generalized connectives, and it is shown that similar dichotomy theorems hold also when some of the variables are assigned constant values. Expand

The Complexity of Minimal Satisfiability Problems

- Computer Science, Mathematics
- STACS
- 2000

The question of whether dichotomy theorems can be proved for these problems was raised at that time, but was left open, and is settled affirmatively by establishing a dichotomy theorem for the class of all MIN SAT(S)-problems. Expand

Linear Time Algorithms for Some Not-All-Equal Satisfiability Problems

- Mathematics, Computer Science
- SAT
- 2003

It is shown that NAESAT can be decided in linear time for monotone formulas in which each clause has length exactly k and each variable occurs exactly k times, and bicolorability of k-uniform, k-regular hypergraphs is decidable inlinear time. Expand

Dichotomy Theorem for the Generalized Unique Satisfiability Problem

- Mathematics, Computer Science
- FCT
- 1999

This paper presents a dichotomy theorem for the unique satisfiability problem, partitioning the instances of the problem between the polynomial-time solvable and coNP-hard cases and noticing that the additional knowledge of a model makes this problem co NP-complete. Expand

A Hierarchy of Tractable Subclasses for SAT and Counting SAT Problems

- Mathematics, Computer Science
- 2009 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing
- 2009

A new hierarchy of propositional formulĂ¦ subclasses for which the SAT and counting SAT problems can be solved in polynomial time is presented and an efficient algorithm to approximate the number of assignments for any arbitrary conjunctive normal form propositional formula by an upper bound is given. Expand

Boolean Constraint Satisfaction Problems: When Does Post's Lattice Help?

- Mathematics, Computer Science
- Complexity of Constraints
- 2008

For us central family of algorithmic problems, parameterized by aconstraint language Î“, now is the problem to determinesatisfiability of a given Î“-formula, denoted by Csp(Î“). Expand

Maximum Exact Satisfiability: NP-completeness Proofs and Exact Algorithms

- Mathematics
- 2004

Inspired by the Maximum Satisfiability and Exact Satisfiability problems we present two Maximum Exact Satisfiability problems. The first problem called Maximum Exact Satisfiability is: given aâ€¦ Expand

A perspective on certain polynomial-time solvable classes of satisfiability

- Mathematics, Computer Science
- Discret. Appl. Math.
- 2003

The scope of certain well-studied polynomial-time solvable classes of Satisfiability is investigated and it is found that the matched formulas are more numerous than Horn, extended Horn, renamable Horn, q-Horn, CC-balanced, or single lookahead unit resolution (SLUR) formulas. Expand

Dichotomy Theorems for Alternation-Bounded Quantified Boolean Formulas

- Computer Science, Mathematics
- ArXiv
- 2004

This paper proves dichotomy theorems for alternation-bounded quantified generalized Boolean formulas by showing that these problems are either $\Sigma_i^p$-complete or in P, and gives a simple criterion to determine which of the two cases holds. Expand

#### References

SHOWING 1-10 OF 23 REFERENCES

Complete problems for deterministic polynomial time

- Mathematics, Computer Science
- STOC '74
- 1974

Several problems which are complete for P, the class of languages recognizable in deterministic polynomial time, are introduced, to serve to differentiate those sets in P which are not recognizable in logarithmic space from those which are, providing such differentiation is possible. Expand

The complexity of theorem-proving procedures

- Computer Science, Mathematics
- STOC
- 1971

It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be â€średucedâ€ť to the problem of determining whether a given propositional formula is aâ€¦ Expand

Word problems requiring exponential time(Preliminary Report)

- Computer Science
- STOC
- 1973

A number of similar decidable word problems from automata theory and logic whose inherent computational complexity can be precisely characterized in terms of time or space requirements on deterministic or nondeterministic Turing machines are considered. Expand

Space-Bounded Reducibility among Combinatorial Problems

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 1975

Two versions of the polynomial time-reducibility of Cook and Karp are defined, by means of Turing machines and by bounded-quantifier formulas, and they are shown to be complete for nondeterministic (deterministic) log n space. Expand

A Computing Procedure for Quantification Theory

- Computer Science
- JACM
- 1960

In the present paper, a uniform proof procedure for quantification theory is given which is feasible for use with some rather complicated formulas and which does not ordinarily lead to exponentiation. Expand

A note on disjunctive form tautologies

- Computer Science, Mathematics
- SIGA
- 1973

Cook [1] and Karp [2] have shown that a large class of combinatorial decision problems can be solved in time bounded by a polynomial in the size of the problem iff there is a polynomial timeâ€¦ Expand

The Polynomial-Time Hierarchy

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1976

The problem of deciding validity in the theory of equality is shown to be complete in polynomial-space, and close upper and lower bounds on the space complexity of this problem are established. Expand

Complexity of decision problems based on finite two-person perfect-information games

- Computer Science
- STOC '76
- 1976

We present a number of simply-structured combinatorial games for which the problem of determining the outcome of optimal play is complete in polynomial spaceâ€”a condition which gives very strongâ€¦ Expand

Relationships Between Nondeterministic and Deterministic Tape Complexities

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 1970

The amount of storage needed to simulate a nondeterministic tape bounded Turingmachine on a deterministic Turing machine is investigated and a specific set is produced, namely the set of all codings of threadable mazes, such that, if there is any set which distinguishes nondeter microscopic complexity classes from deterministic tape complexity classes, then this is one such set. Expand

The two-valued iterative systems of mathematical logic

- Mathematics
- 1942

*Frontmatter, pg. i*CONTENTS, pg. vi*INTRODUCTION, pg. 1*Part I. PRELIMINARIES, pg. 10*PART II. DERIVATION OP CLOSED SYSTEMS, pg. 43*PART III. CO-ORDINATION AND APPLICATION, pg. 96*BIBLIOGRAPHY, pg.â€¦ Expand