Counting problem (complexity)

In computational complexity theory and computability theory, a counting problem is a type of computational problem that is obtained by strengthening a decision problem.

For example, the SAT problem asks: "Given a Boolean formula, is there a truth-value assignment such that it evaluates to True?". The corresponding counting problem, called #SAT, asks: "Given a Boolean formula, how many truth-value assignments are there such that it evaluates to True?".

And in general, the counting problem corresponding to a decision problem X is called #X, where # is the number sign.

Counting complexity techniques have significant applications in clarifying the relation between complexity classes of P, NP, PH, etc, in circuit complexity, and in interactive proof systems.