Sharp-SAT
Encyclopedia
In computational complexity theory
, #SAT, or Sharp-SAT, a function problem
related to the Boolean satisfiability problem
, is the problem of counting the number of satisfying assignments of a given Boolean formula. It is well-known example for the class of counting problem
s, which are of special interest in computational complexity theory.
It is a #P-complete problem, as any NP machine can be encoded into a Boolean formula by a process similar to that in Cook's theorem
, such that the number of satisfying assignments of the Boolean formula is equal to the number of accepting paths of the NP machine. Any formula in SAT can be rewritten
as a formula in 3-CNF
form preserving the number of satisfying assignments, and so #SAT and #3SAT are equivalent and #3SAT is #P-complete as well.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, #SAT, or Sharp-SAT, a function problem
Function problem
In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO...
related to the Boolean satisfiability problem
Boolean satisfiability problem
In computer science, satisfiability 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...
, is the problem of counting the number of satisfying assignments of a given Boolean formula. It is well-known example for the class of counting problem
Counting problem
Counting problem may refer to:* Enumeration* Combinatorial enumeration* Counting problem...
s, which are of special interest in computational complexity theory.
It is a #P-complete problem, as any NP machine can be encoded into a Boolean formula by a process similar to that in Cook's theorem
Cook's theorem
In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete...
, such that the number of satisfying assignments of the Boolean formula is equal to the number of accepting paths of the NP machine. Any formula in SAT can be rewritten
3sat
3sat is the name of a public, advertising-free, television network in Central Europe. The programming is in German and is broadcast primarily within Germany, Austria and Switzerland .3sat was established for cultural...
as a formula in 3-CNF
Conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form if it is a conjunction of clauses, where a clause is a disjunction of literals.As a normal form, it is useful in automated theorem proving...
form preserving the number of satisfying assignments, and so #SAT and #3SAT are equivalent and #3SAT is #P-complete as well.