In computer science, satisfiability ( often written in all capitals or abbreviated SAT ) is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE.

To emphasize the binary nature of this problem, it is frequently referred to as Boolean or propositional satisfiability.

In complexity theory, the satisfiability problem ( SAT ) is a decision problem, whose instance is a Boolean expression written using only AND, OR, NOT, variables, and parentheses.

The Boolean satisfiability problem is NP-complete.

The propositional satisfiability problem ( PSAT ), which decides whether a given propositional formula is satisfiable, is of central importance in various areas of computer science, including theoretical computer science, algorithmics, artificial intelligence, hardware design, electronic design automation, and verification.

There are several special cases of the Boolean satisfiability problem in which the formula are required to be conjunctions of clauses ( i. e. formulae in conjunctive normal form ).

Determining the satisfiability of a formula in conjunctive normal form where each clause is limited to at most three literals is NP-complete ; this problem is called " 3SAT ", " 3CNFSAT ", or " 3-satisfiability ".

Determining the satisfiability of a formula in which each clause is limited to at most two literals is NL-complete ; this problem is called " 2SAT ".

Determining the satisfiability of a formula in which each clause is a Horn clause ( i. e. it contains at most one positive literal ) is P-complete ; this problem is called Horn-satisfiability.

The Cook – Levin theorem states that the Boolean satisfiability problem is NP-complete, and in fact, this was the first decision problem proved to be NP-complete.

It can be seen as P's version of the Boolean satisfiability problem.

Schaefer's dichotomy theorem states that, for any restriction to Boolean operators that can be used to form these subformulae, the corresponding satisfiability problem is in P or NP-complete.

The maximum satisfiability problem, an FNP generalization of SAT, asks for the maximum number of clauses which can be satisfied by any assignment.

Propositional satisfiability has various generalisations, including satisfiability for quantified Boolean formula problem, for first-and second-order logic, constraint satisfaction problems, 0-1 integer programming, and maximum satisfiability problem.

simple: Boolean satisfiability problem

For example, P < sup > SAT </ sup > is the class of problems solvable in polynomial time by a deterministic Turing machine with an oracle for the Boolean satisfiability problem.

( Boolean satisfiability problem )

It is a special case of the general Boolean satisfiability problem, which can involve constraints on more than two variables, and of constraint satisfaction problems, which can allow more than two choices for the value of each variable.

To learn more information about the SAT problem, read the Boolean satisfiability problem article.

An interpretation of this theoretical result in layman's terms is that this puzzle is as hard to solve as the Boolean satisfiability problem, which is a well studied difficult problem in computer science.

But the archetypal PSPACE-complete problem is generally taken to be the quantified Boolean formula problem ( usually abbreviated to QBF or TQBF ; the T stands for " true "), a generalization of the first known NP-complete problem, the Boolean satisfiability problem ( SAT ).

It is very easy to determine the satisfiability of a boolean formula in DNF: such a formula is satisfiable if and only if it contains a satisfiable conjunction ( one that does not contain a variable and its negation ), whereas counting the number of satisfying assignments is # P-complete.

* Boolean satisfiability problem, determining if the variables of a Boolean formula can be assigned to make the formula evaluate to True

# The boolean satisfiability problem, in which a candidate solution is a truth assignment, and the target is to maximize the number of clauses satisfied by the assignment ; in this case, the final solution is of use only if it satisfies all clauses

More precisely, if m / n is fixed as a constant α ≠ 1, the probability of satisfiability tends to a limit as n goes to infinity: if α < 1, the limit is one, while if α > 1, the limit is zero.

Other connections to unparameterised computational complexity are that FPT equals W if and only if circuit satisfiability can be decided in time, or if and only if there is a computable, nondecreasing, unbounded function f such that all languages recognised by a nondeterministic polynomial-time Turing machine using f ( n ) log n nondeterministic choices are in P.

An important consequence of the theorem is that if there exists a deterministic polynomial time algorithm for solving Boolean satisfiability, then there exists a deterministic polynomial time algorithm for solving all problems in NP.

Then the expression can be satisfied if and only if there is a way for the machine to run correctly and answer " yes ", so the satisfiability of the constructed expression is equivalent to asking whether or not the machine will answer " yes ".

For example, it's quite possible to reduce a difficult-to-solve NP-complete problem like the boolean satisfiability problem to a trivial problem, like determining if a number equals zero, by having the reduction machine solve the problem in exponential time and output zero only if there is a solution.

A polynomial-time algorithm for Horn satisfiability is based on the rule of unit propagation: if the formula contains a clause composed of a single literal ( a unit clause ), then all clauses containing ( except the unit clause itself ) are removed, and all clauses containing have this literal removed.

To prove this, we show that the NP-complete satisfiability problem belongs to PP.

Note that the tautology problem for positive Boolean formulae remains co-NP complete, even though the satisfiability problem is trivial, as every positive Boolean formula is satisfiable.

The Mastermind satisfiability problem is a decision problem that asks, " Given a set of guesses and the number of colored and white pegs scored for each guess, is there at least one secret pattern that generates those exact scores?

( 1984 ), " Linear-time algorithms for testing the satisfiability of propositional Horn formulae ".

To understand the early history of model theory one must distinguish between syntactical consistency ( no contradiction can be derived using the deduction rules for first-order logic ) and satisfiability ( there is a model ).

As observes, it can also be seen as an instance of the Davis – Putnam algorithm for solving satisfiability problems using the principle of resolution.

This immediately leads to a linear time algorithm for testing satisfiability of 2-CNF formulae: simply perform a strong connectivity analysis on the implication graph and check that each variable and its negation belong to different components.

Perhaps the simplest problem for alternating machines to solve is the quantified boolean formula problem, which is a generalization of the boolean satisfiability problem in which each variable can be bound by either an existential or a universal quantifier.

The Horn satisfiability problem can also be asked for propositional many-valued logics.

He argues ( contra Hintikka ) that while satisfiability might be a first-order matter, the question of whether there is a winning strategy for Verifier over all structures in general " lands us squarely in full second order logic " ( emphasis Feferman's ).

For example, the Boolean satisfiability problem can be reduced to the halting problem by transforming it to the description of a Turing machine that tries all truth value assignments and when it finds one that satisfies the formula it halts and otherwise it goes into an infinite loop.

The boolean satisfiability problem can be viewed as the special case where all variables are existentially quantified, allowing ordinary nondeterminism, which uses only existential branching, to solve it efficiently.

Some P system variants are known to be capable of solving the SAT ( boolean satisfiability ) problem in linear time and, owing to all NP-complete problems being equivalent, this capability then applies all such problems.

In his 1972 paper, " Reducibility Among Combinatorial Problems ", Richard Karp used Stephen Cook's 1971 theorem that the boolean satisfiability problem is NP-complete ( also called the Cook-Levin theorem ) to show that there is a polynomial time many-one reduction from the boolean satisfiability problem to each of 21 combinatorial and graph theoretical computational problems, thereby showing that they are all NP-complete.

The study of algorithms to automatically discover interpretations of theories that render all sentences as being true is known as the satisfiability modulo theories problem.

In other words, iteratively applying the resolution rule in a suitable way allows for telling whether a propositional formula is satisfiable and for proving that a first-order formula is unsatisfiable ; this method may prove the satisfiability of a first-order satisfiable formula, but not always, as it is the case for all methods for first-order logic ( see Gödel's incompleteness theorems and Halting problem ).