go-v.orgcodex
Menu
Page tools

codex · Philosophy

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.

Wikipedia contributors, "Counting problem (complexity)", Wikipedia, revision 1381004814, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex