blob: eabdcfe3d6a31b6f3078b39bdb9e4b178257671c (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
+++
title = "SAT Solvers"
author = "Yann Herklotz"
tags = []
categories = []
backlinks = ["2d"]
forwardlinks = ["2d2"]
zettelid = "2d1"
+++
SAT is a mathematical problem whereby the question is asked whether a
logical formula is satisfiable, meaning there is a combination of inputs
that will satisfy the sentence. This logical formula is often expressed
in conjunctive normal form (CNF).
SAT solvers are programs that can solve these problems automatically.
Even though it is an intractable problem and is in O(2^n^) for the
number of variables present in the sentence, there are efficient
algorithms that will work well most of the time.
|
