2UN-SAT Created 2026-10-07 Updated 2026-10-14
Satisfiability of conjunctive normal form formulas whose clauses have at most two unnegated variables. It is NP-complete: binary AND/OR and unary NOT gate equivalences in a Tseitin transformation already satisfy that restriction. Clauses may contain arbitrarily many negative literals; the total clause width is not restricted to two.
3-SAT 2026-10-06
3-SAT is the Boolean satisfiability problem restricted to Boolean formulas in conjunctive normal form with at most three Boolean literals per Boolean clause. It is NP-complete. A nonempty short Boolean clause can be padded to three positions by repeating a Boolean literal, without changing satisfiability.
Boolean satisfiability problem Created 2026-09-24 Updated 2026-10-18
The Boolean satisfiability problem asks whether a Boolean formula has an assignment making it true. A complete assignment is a Boolean valuation: it gives every Boolean variable a truth value, consistently at all occurrences. A satisfying assignment, also called a model of a Boolean formula, makes the entire Boolean formula true. A solver's answer SAT asserts that at least one satisfying assignment exists; UNSAT asserts that the input is an unsatisfiable Boolean formula. These are statements about existence, rather than the truth value under one particular Boolean valuation.
For conjunctive normal form, or CNF, write
Each Boolean literal is a Boolean variable or its logical negation. Each Boolean clause uses inclusive logical disjunction: one true Boolean literal suffices. The outer logical conjunction requires every Boolean clause to succeed under the same Boolean valuation. Choosing a different Boolean valuation for each Boolean clause would answer a different question.
Consider the original three-Boolean variable example
At the Boolean valuation , the Boolean literals in have values , those in have values , and those in have values . Every Boolean clause therefore has truth value one, so has truth value one: this is a satisfying assignment.
The complete truth table has Boolean valuations. Exactly two are satisfying assignments: and . In particular, satisfies the first two Boolean clauses but falsifies the third, so satisfying most Boolean clauses does not suffice for SAT. That different objective belongs to maximum satisfiability.
Figure 2.
All eight Boolean valuations of the original CNF example, with its two satisfying assignments highlighted
. Details.
A short proof of completeness avoids listing all eight rows. If , the Boolean clause forces , after which forces ; is already true. If , forces , after which forces ; is already true. These two cases exhaust the truth values of and produce precisely the two satisfying assignments above.
Verifying a satisfying assignment and finding a satisfying assignment are different tasks. Given a candidate, evaluate the Boolean formula once; finding a candidate requires choosing compatible truth values across all its Boolean clauses. The Cook-Levin theorem says that general SAT is NP-complete, even though a proposed satisfying assignment is efficiently checkable. Its proof encodes a bounded nondeterministic computation as a Boolean formula whose satisfying assignments describe accepting computations. Stephen A. Cook's 1971 paper established this connection between computational complexity theory and propositional logic.[ref]
A concrete use is checking finite configuration rules. Let mean that an optional feature is enabled, that a fallback is selected, and that the feature's required component is installed. Require a feature or fallback, require the component whenever the feature is enabled, and forbid using the fallback with that component. Logical implication rewrites the second rule as ; De Morgan's laws rewrite the third rule as . Their logical conjunction is exactly , so its two satisfying assignments give the two allowed configurations. The usefulness of SAT lies in expressing local rules uniformly while demanding one globally consistent Boolean valuation. The conclusion concerns exactly these encoded rules.
Clausal form 2026-10-31
A representation by a set of first-order clauses, interpreted as their logical conjunction. General first-order formulas can be transformed by Skolemization and conversion to conjunctive normal form, preserving satisfiability in an expanded first-order signature.
In an expanded signature, Skolemization preserves equisatisfiability rather than equivalence under arbitrary interpretations of the new function symbols.
Clique decision problem 2026-10-31
Given an explicitly represented finite simple graph and a nonnegative integer , decide whether contains a clique of size . The problem is NP-complete. A polynomial-time many-one reduction from SAT first obtains conjunctive normal form by a Tseitin transformation, makes one vertex per Boolean literal occurrence, and joins noncontradictory occurrences from different Boolean clauses. A clique as large as the Boolean clause count is equivalent to a satisfying assignment.
Conjunctive normal form Created 2026-10-06 Updated 2026-10-18
A Boolean formula is in conjunctive normal form when it is a logical conjunction of Boolean clauses. It is true precisely when every Boolean clause is true under the same Boolean valuation; an empty logical conjunction is true. For example, has two Boolean clauses with widths two and one. Width counts Boolean literal occurrences within a Boolean clause, whereas the Boolean clause count counts the conjuncts. 2-SAT bounds width by two, and 3-SAT bounds width by three. A Boolean formula with an empty Boolean clause is an unsatisfiable Boolean formula.
Cook-Levin theorem Created 2026-10-07 Updated 2026-10-14
Every NP verifier can be compiled into a polynomial-size Boolean circuit whose inputs encode its certificate, and then into an equisatisfiable conjunctive normal form by a Tseitin transformation. This gives a polynomial-time many-one reduction from every NP language to SAT. Checking a guessed assignment proves membership, so SAT is NP-complete.
Disjunctive normal form Created 2026-10-14 Updated 2026-10-31
A Boolean formula is in disjunctive normal form when it is a disjunction of conjunctions of Boolean literals. Width bounds the number of literals in each conjunction, not the number of conjunctions. A depth- decision tree gives such a formula of width at most by taking the disjunction of its accepting leaf conditions; rejecting leaves give the dual conjunctive normal form.
Exactly-one constraint 2026-10-25
A restriction requiring exactly one member of a set of Boolean variables to be true. A direct conjunctive normal form encoding combines one at-least-one Boolean clause, , with at-most-one Boolean clauses, for . The first supplies existence and the second supplies uniqueness. For , the empty at-least-one Boolean clause correctly makes the condition unsatisfiable.
Maximum satisfiability 2026-10-14
Maximum satisfiability asks for a truth assignment maximizing the number of true clauses of a conjunctive normal form formula. The Boolean satisfiability problem asks whether all its clauses can be made true. Binary clause indicators give an integer programming formulation, and the literal-frequency greedy approximation for MAX-SAT guarantees at least half the optimum. Counts of clauses, rather than multiplicities of repeated literals within one clause, are relevant to this objective.
The clique decision problem belongs to NP. First reject . Otherwise a complexity certificate lists distinct vertices. Check distinctness and test that each of the pairs is an edge. Under a conventional explicit graph encoding, the complexity certificate length and verification time complexity are polynomial in the input length. The early rejection is relevant when is given in the binary numeral system.
For NP-hardness, first transform a SAT instance into an equisatisfiable conjunctive normal form of polynomial size using a Tseitin transformation. This step avoids the possibly exponential increase caused by distributing arbitrary Boolean formulas into conjunctive normal form. Introduce a fresh Boolean variable for each subformula, constrain it to have the connective's truth value using a constant number of Boolean clauses, and require the top variable to be true. A Boolean valuation of the original Boolean variables satisfies the original Boolean formula exactly when it extends to a satisfying assignment of these constraints.
Create one vertex for each occurrence of a Boolean literal in each Boolean clause. Join two such vertices by an edge exactly when they belong to different Boolean clauses and their Boolean literals are not a variable and its logical negation. Set . There are at most as many vertices as Boolean literal occurrences and at most quadratically many edges, so this construction takes polynomial time.
If has a satisfying assignment, choose one true Boolean literal occurrence from each Boolean clause. No two selected Boolean literals are contradictory, so their vertices form a clique. Conversely, an -clique contains at most one vertex from each Boolean clause, because there are no edges within a Boolean clause. It therefore selects exactly one occurrence from each of the Boolean clauses. The selected Boolean literals are pairwise noncontradictory, so assign their Boolean variables the indicated truth values and assign any other Boolean variables arbitrarily. This Boolean valuation satisfies every Boolean clause.
An empty Boolean clause gives no vertex in its group, correctly preventing an -clique. An empty logical conjunction can instead be mapped to a fixed yes-instance, avoiding any convention about . Malformed SAT descriptions can be mapped to a fixed no-instance. We have proved
An exponential increase is unavoidable for an equivalent conjunctive normal form over the original variables. Consider the linear-size Boolean formula
Distributing gives the Boolean clauses
To prove that the growth is necessary, fix one choice . Let make every false and its partner true. Each pair then contains a false variable, so is false. Any equivalent conjunctive normal form must contain a Boolean clause falsified by and entailed by .
Every individual term entails , because that term implies . After tautological Boolean clauses are discarded, this forces to contain a positive or positive for every : otherwise set both variables in that pair true and independently falsify all Boolean literals of , contradicting the entailment. Since is false at , it must contain the false member , never its true partner. Consequently the same cannot be false at any different . The different assignments therefore require at least different Boolean clauses.
Writing the answer already takes . This obstruction applies to first-order logic as well, since the example can be expressed using ground unary atomic formulas. It concerns exact equivalence without auxiliary symbols. A Tseytin transformation can produce a polynomial-size equisatisfiable conjunctive normal form with auxiliary variables, so the statement must not be extended to that different task.
Apply the distributive law of Boolean algebra to the two logical conjunctions. With , , , and , the identity gives
The second step uses complementation and commutativity in Boolean algebra; the last uses the identity law for logical conjunction. The result is in conjunctive normal form: its first Boolean clause requires at least one input to be true, and its second Boolean clause prohibits both inputs being true. Together they express exclusive or.
Replace each implication by a logical disjunction and use the conjunctive normal form for exclusive or from part (a). The resulting Boolean clauses are
Here the displayed array is a list of the six Boolean clauses, whose logical conjunction is equivalent to all four constraints.
Use resolution first on , then on , and finally on :
Removing the repeated Boolean literal in the final Boolean clause uses idempotence. Neither nor is needed: even the weaker assumptions that the coin has at least one outcome and that at least one person wins already force , once the two implications hold.
Use a sequential SATPlan encoding with times . The fluent universe is
There are nine support Boolean variables and three clearance Boolean variables per time layer. Static block types, parameter inequalities and permanent table availability are handled during action grounding. For each well-typed ground action from parts (b)–(c), introduce an occurrence Boolean variable for . Allow at most one action per layer, including no action, so that a horizon of encodes at most physical actions.
The complete initial-state formula is
Every well-typed fluent not initially true is explicitly false. The final goal formula is simply . Leaving unrelated final facts unconstrained is appropriate; leaving unrelated initial facts unconstrained would introduce imaginary starting states.
For each , include all action precondition axioms , after removing static true conditions. For example,
The precondition axiom for similarly requires .
For every fluent , let be the logical disjunction of actions at adding , and the logical disjunction deleting it. Include the successor-state axiom
It combines action effects with the frame axiom, preventing unsupported changes. A fully grounded example is
Apply the same construction to every support and clearance fluent, using the exact add/delete lists. If no action occurs, both effect logical disjunctions are false, so all fluents persist.
The sequential action exclusion axioms are for every pair of distinct grounded actions . For example,
forbids selecting those two occurrences together. Do not add a requirement that some action occur in every layer: that would remove idle padding and change “at most ” into an exact-length requirement. One may additionally include true planning state invariants, such as a block having at most one support and a block support carrying at most one block; the unlimited table must be exempt from the latter restriction.
Finally, conjoin , , and all precondition, successor and exclusion formulas over the layers to obtain . It is a propositional formula; if a solver requires conjunctive normal form, use a satisfiability-preserving Tseitin transformation with auxiliary Boolean variables. The equivalence between this encoding and real action sequences follows from sequential SATPlan correctness: a satisfying assignment induces exactly the stated STRIPS trajectory, and every sufficiently short valid plan supplies such an assignment.
Use an exactly-one constraint for each finite-domain variable and a Boolean clause forbidding each disallowed constraint tuple. Let the variables be , with explicitly listed finite constraint domains , and let constraint have distinct-variable scope and allowed relation . Introduce a Boolean variable for every , interpreted as . The direct SAT encoding of finite-domain constraints is
In the middle logical conjunction, each unordered distinct pair is included once. The first Boolean clause requires at least one value, the pairwise Boolean clauses permit at most one, and a final Boolean clause is false exactly when all coordinates of one forbidden tuple are selected. The formula is in conjunctive normal form. An empty constraint domain produces an empty Boolean clause, correctly making the instance unsatisfiable.
For soundness of the reduction, a solution of the constraint satisfaction problem gives the Boolean valuation exactly when . Every exactly-one constraint holds; a forbidden tuple differs from on at least one scoped coordinate, making its negative Boolean clause true. Thus supplies a satisfying assignment for .
Conversely, a satisfying assignment selects a unique value for every . If a constraint failed, the selected scoped tuple would belong to , and its entire negative Boolean clause would be false. That contradicts satisfiability. Hence is a solution. Decoding takes by scanning the value indicators. This proves has a solution if and only if is satisfiable.
For explicit size accounting, put , and . There are Boolean variables,
Boolean clauses, and
literal occurrences. These formulas count nonempty scopes; a false zero-arity constraint contributes an empty Boolean clause, while a true one contributes none. Formula storage is literal-sized records; a bit-level encoding also stores indicator indices. With maximum constraint domain size , constraints and maximum arity , this is bounded by for nontrivial domains and scopes. In the common binary case it is .
The input representation matters: listing all forbidden tuples costs up to tests per constraint. This is polynomial for bounded arity and explicitly represented domains, but can be exponential in the description length of a succinct high-arity constraint. The translation is valid in that case without constituting a polynomial-size reduction. If a compact constraint is supplied as a polynomial-size Boolean circuit, one may instead encode that circuit using auxiliary Boolean variables and local conjunctive normal form equivalences, with size proportional to the circuit. No compact representation is silently assumed.
For the instance in (c), after unary filtering there are indicators. The five at-least-one Boolean clauses, pairwise at-most-one Boolean clauses and forbidden-equality Boolean clauses give Boolean clauses. Setting only true encodes the displayed solution.
A conjunctive normal form is a finite conjunction of clauses, each clause being a finite disjunction of literals. A literal is a propositional variable or the negation of one. Thus its shape is
A single clause or single literal is allowed; the necessary parentheses can be inserted according to the grammar.
First eliminate implication and biconditional using the logical equivalences
Push negations inwards using De Morgan's laws and eliminate double negations. Structural induction leaves only literals joined by conjunction and disjunction.
Now induct on that remaining expression. A literal is already in conjunctive normal form. A conjunction of two conjunctive normal forms is again one after associating its clauses. For a disjunction, write the two inductively obtained forms as and and use distributivity:
Each is a clause. All operations preserve logical equivalence, proving the required form exists.