Boolean satisfiability problem
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called satisfiable. On the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is unsatisfiable. For example, the formula "a AND NOT b" is satisfiable because one can find the values a = TRUE and b = FALSE, which make (a A
academic discipline
Wikipage disambiguates
1-in-3-SAT3-SAT3-satisfiability3SAT3cnf3cnf-sat3cnfsatAlgorithms for solving SATAlgorithms for solving the boolean satisfiability problemBoolean SATBoolean SAT solverBoolean SatisfiabilityBoolean satisfiabilityCNF-SATCNFSATCounted Boolean Satisfiability ProblemK-SATK-cnf-satLinear SATList of SAT solversMethods for solving SATOne-in-three 3SATParallel SAT solverPropositional satisfiabilitySAT-solverSAT SolverSAT problemSAT solverSAT solvingSatisfiability ProblemSatisfiability of boolean expressionsUnambiguous SATUnique-SATXOR-SATXOR-satisfiability
Wikipage redirect
1-in-3-SAT2-satisfiability3-SAT3-dimensional matching3-satisfiability3SAT3cnf3cnf-sat3cnfsatAPXAcryditeAction languageAction model learningAlgorithm selectionAlgorithmic Lovász local lemmaAlgorithmic efficiencyAlgorithms for solving SATAlgorithms for solving the boolean satisfiability problemAlloy (specification language)Alternating Turing machineAnd-inverter graphAnswer set programmingArmin GruenAutomated planning and schedulingAutomated reasoningAutomatic test pattern generationBSATBart SelmanBelief revisionBetweennessBinary decision diagramBook embeddingBoole's expansion theoremBooleanBoolean Pythagorean triples problemBoolean SATBoolean SAT solverBoolean SatisfiabilityBoolean algebraBoolean satisfiability
Link from a Wikipage to another Wikipage
class
seeAlso
primaryTopic
Boolean satisfiability problem
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called satisfiable. On the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is unsatisfiable. For example, the formula "a AND NOT b" is satisfiable because one can find the values a = TRUE and b = FALSE, which make (a A
has abstract
Das Erfüllbarkeitsproblem der ...... gs- und Schedulingalgorithmen.
@de
En informatique théorique, le ...... et on utilise un solveur SAT.
@fr
En teoria de complexitat compu ...... ions automàtiques de teoremes.
@ca
En teoría de la complejidad co ...... se de complejidad NP-completo.
@es
In de complexiteitstheorie ver ...... de gehele propositie waar is.
@nl
In logic and computer science, ...... and automatic theorem proving.
@en
La soddisfacibilità booleana, ...... ormula è identicamente falsa).
@it
Na teoria da complexidade comp ...... veis recebem valores binários.
@pt
Problem spełnialności – zagadn ...... dukcji w czasie wielomianowym.
@pl
Problém splnitelnosti booleovs ...... lastech umělé inteligence, a .
@cs
Link from a Wikipage to an external page
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
1,025,391,487
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
subject
hypernym
type
comment
Das Erfüllbarkeitsproblem der ...... dass zu wahr ausgewertet wird?
@de
En informatique théorique, le ...... les qui rend la formule vraie.
@fr
En teoria de complexitat compu ...... no es pot satisfer en cap cas.
@ca
En teoría de la complejidad co ...... se de complejidad NP-completo.
@es
In de complexiteitstheorie ver ...... de gehele propositie waar is.
@nl
In logic and computer science, ...... and b = FALSE, which make (a A
@en
La soddisfacibilità booleana, ...... ormula è identicamente falsa).
@it
Na teoria da complexidade comp ...... fórmula como verdadeira, ela é
@pt
Problem spełnialności – zagadn ...... ność obliczeniową wykładniczą.
@pl
Problém splnitelnosti booleovs ...... dřuje protimluv, kontradikci).
@cs
label
Boolean satisfiability problem
@en
Bulea plenumebloproblemo
@eo
Erfüllbarkeitsproblem der Aussagenlogik
@de
Problem spełnialności
@pl
Problema de satisfacibilidad booleana
@es
Problema de satisfacibilitat booleana
@ca
Problema de satisfatibilidade booliana
@pt
Problème SAT
@fr
Problém splnitelnosti booleovské formule
@cs
Soddisfacibilità booleana
@it