Decision asks whether a witness exists; counting asks how many there are. A separate change of viewpoint replaces one algorithm for every input length by a family of Boolean circuits, one circuit for each length. These two extensions of the basic model reveal different sources of difficulty. Counting measures the size of the solution space, so its output contains more information than the single bit that records whether the space is nonempty. Nonuniform circuits, by contrast, relax the requirement that a single finite description handle all input lengths, and this relaxation changes what "efficient" means in a way that has no analogue in the uniform Turing machine model. This unit develops both ideas carefully, states exactly which hypotheses are used, and separates what is proved here from what is cited as background.
Why count, and why use circuits?
Consider a Boolean formula that arises from a scheduling or configuration problem. A solver that answers "is there a valid schedule?" gives one bit of information. In applications one often wants more: how many valid schedules exist, what fraction of all assignments are valid, or how likely a random assignment is to succeed. These are counting questions. They are also natural mathematically, because the number of accepting paths of a nondeterministic machine is a well-defined function of the input, and the function can be studied by the same reduction-based methods used for languages.
Circuits address a different issue. A Turing machine is a single finite object that must work for inputs of every length. A circuit is a finite object for one length only. If we ask how many gates are needed to compute a function on bits, we obtain a combinatorial measure that can be studied without reference to any machine. The price is that the sequence of circuits need not be generated by any rule. Understanding exactly what is gained and lost by dropping that rule is the second theme of this unit.
The two themes meet at a common point. In both cases the decision question for a language is replaced by a richer object: a function from strings to numbers in the first case, a sequence of finite objects in the second. In both cases the comparison with the familiar class requires care about what exactly is being measured.
Counting witnesses
Definition 5.1.1
(The class #P)
A function belongs to if there is a nondeterministic polynomial-time Turing machine for which is the number of accepting computation paths on input . Equivalently, with a polynomial-time verifier and a fixed polynomial witness length, it counts accepting witnesses. The fixed-length convention ensures each witness identifies one path.
The equivalence of the two descriptions rests on a bookkeeping point. In the verifier formulation there is a polynomial-time predicate and a polynomial such that
Because every witness has exactly the same length , distinct witnesses are distinct binary strings, and a nondeterministic machine that guesses and then runs has one path per witness. If witnesses had variable length, one string could be a prefix of another, and the correspondence between witnesses and paths would require a separate argument. Note also that , so the value of has polynomially many bits; this is why exact counting functions are written with polynomially many output bits.
For a Boolean formula with a specified list of variables, counts satisfying assignments to that list. The list matters: adding an unused variable doubles the count although satisfiability is unchanged. The decision problem SAT asks only whether the count is positive. A polynomial-time exact counting algorithm would therefore decide SAT, but the reverse implication is not established by this observation.
The relationship can be stated as a precise one-directional comparison. If were computable in polynomial time, then on input with variable list we would compute and accept exactly when it is nonzero, which decides SAT. Nothing in this argument runs backwards: an oracle that merely reports whether a satisfying assignment exists does not obviously reveal how many exist. The counting identities below instead illuminate how the numbers of witnesses combine.
An example
Worked example 5.1.2
(Counting assignments)
For on the specified variables , the two clauses together force while is arbitrary. Thus . On the variable list the same expression has count , because either value of unused extends each satisfying assignment.
The pattern behind this example is general. If has satisfying assignments on a list of variables and we append further variables that do not occur in , then each satisfying assignment extends in ways, so the new count is . Conversely, a formula with count on variables has density among all assignments, and this density is unchanged by appending unused variables. The density is therefore the quantity that is invariant under the choice of variable list, while the raw count is not.
Two further counting computations
Worked example 5.1.3
(Counting a parity-constrained formula)
Let on the variable list , where is exclusive or. The first conjunct holds exactly when , and the second exactly when . Choose freely. Then and are forced. Hence there are exactly two satisfying assignments, namely and , and . A check by enumeration of all assignments confirms this: the assignments , , , , , each violate one of the two conditions, leaving the two listed. The density is .
Worked example 5.1.4
(Counting by cases and complement)
Let on the variable list . A satisfying assignment must make at least two of the three variables true, because if at most one variable is true then the clause omitting that variable (or any clause, when none is true) is falsified. Conversely, if at least two variables are true, every pair of variables contains a true one, so all three clauses hold. Count assignments with at least two true variables: exactly two true gives assignments, and all three true gives . Hence . As a cross-check by complement, the falsifying assignments are those with at most one true variable: , and , as required.
These computations are easy only because the formulas are tiny and highly structured. For a general CNF formula with hundreds of variables, no general polynomial-time exact counting method is known, which is part of what makes interesting.
Counts of variable-disjoint formulas
The following identities describe how counts combine when formulas use disjoint variables.
Proposition 5.1.5
(Counts of conjunctions and disjunctions of variable-disjoint formulas)
Let be a Boolean formula over the variable list and a Boolean formula over a list , where and share no variable. Write the counts on the right below using their own respective lists and . Then on the combined list ,
Moreover, with the same hypotheses, .
Proof
(Proof)
An assignment to the combined list is a pair with assigning and assigning . Because mentions only , its truth value at depends only on ; likewise the truth value of depends only on . Let and , so and on their own lists.
For the conjunction, satisfies exactly when and , so the satisfying set is the Cartesian product , which has elements.
For the disjunction, satisfies exactly when or . The set of pairs with is , of size . The set with is , of size . Their intersection is , of size . Inclusion and exclusion gives .
Proof X-ray
Where variable-disjointness is used
The whole proof rests on one reduction: a pair satisfies exactly when , and satisfies exactly when . This holds because does not mention and does not mention , and it is the only place where the hypothesis is used. Once it is available, the conjunction is the product set , and the disjunction is the union of the two cylinders and . The size of the union is not the sum of the cylinder sizes, because the cylinders overlap exactly in ; inclusion and exclusion removes that overlap once. If and shared a variable, "" and "" would no longer be conditions on separate coordinates, the satisfying set would not be a product, and the count of the conjunction could not be read off from the two individual counts.
As a numerical check, take (so , count ) and (so , count ). The disjunction formula gives . Directly, on three variables is false only when and , which is assignments, so it is true on . The two computations agree.
The proposition shows that for variable-disjoint formulas counting factorizes, whereas the decision problem sees only whether each factor is nonzero. It also warns that disjunction does not behave additively: counts of a disjunction depend on the number of variables in each side, which is another instance of the dependence on the variable list.
Circuits and the nonuniform viewpoint
A Boolean circuit is a finite directed acyclic graph of gates whose input nodes carry bits or constants; its size is the number of gates. A circuit family decides a language when gives its correct membership bit for every -bit string. The class consists of languages with polynomial-size circuit families. The family need not be computable from : this is the nonuniform feature. Every language in has polynomial-size circuits by unrolling a polynomial-time computation; we use that simulation theorem without proof.
Spelled out, means there exist a polynomial and circuits such that has at most gates and, for every , if and only if . The quantifier structure is "there exists a sequence", not "there exists an algorithm producing a sequence". This is the only difference from a uniform definition, and the next result shows that it is a substantial one.
Proposition 5.1.6
(Nonuniformity can encode undecidable information)
There is an undecidable unary language in .
Proof
(Proof)
There are uncountably many subsets of but only countably many Turing machines, so choose an undecidable unary language . For each length , let first check that its input bits are all and then output the hardwired bit indicating whether . This circuit has gates. The choice of its hardwired bit need not be computable from , and the family decides on all binary strings. Thus polynomial circuit size alone does not imply decidability.
The construction is worth examining closely. For , the "all inputs are " test is a conjunction of inputs, which needs binary AND gates. The hardwired bit is then either combined by one more AND gate (if ) or replaced by the constant output (if ). The total is at most gates for ; for use the appropriate constant output. The family is certainly polynomial in size. The undecidability enters solely through the sequence , which no algorithm can produce.
Counterexamples and the role of exact hypotheses
Three small observations show why the hypotheses in the preceding statements cannot simply be dropped.
First, the factorization fails without variable-disjointness.
Counterexample mode
Factorization fails when variables are shared
Suppose one claims that for all formulas. Take and on the single-variable list . Then (only ) and (only ), so the product is . But has no satisfying assignment, so its count is . The repair is the hypothesis of the proposition: and must use disjoint variable lists, so that a satisfying pair is an independent choice of a satisfying and a satisfying .
Shared variables couple the factors, which is why the independence of the two choices cannot be assumed.
Second, the count depends on the declared variable list. The formula has count on the list but count on the list . Any statement about that omits the list is ambiguous.
Third, polynomial circuit size without uniformity does not by itself guarantee an algorithm, as the hardwired unary language shows. A uniform family, by contrast, is one for which a polynomial-time machine on input outputs a description of . For such a family the language is in , since one constructs and evaluates it. This is the inclusion from polynomial-time uniform families to . The converse, constructing a polynomial-time uniform family by unrolling a polynomial-time machine, is a standard simulation result used without proof here.
What is cited and not proved here
The permanent of a matrix and the theorem that computing it is -complete are central further examples; Valiant's theorem is not proved here. Nor does this unit prove Toda's theorem or the Karp–Lipton theorem. Those results need precise reductions, oracle conventions, and additional machinery before they can be used responsibly. The unproved dependencies include normalization of nondeterministic machines for the verifier equivalence and the simulation of polynomial-time computation by uniform polynomial-size circuits; everything else, including the multiplicativity proposition and the undecidability example, has been proved from the definitions.
Common mistake
(Circuits are not automatically uniform algorithms)
A polynomial bound on the size of each circuit does not provide a polynomial-time procedure to construct that circuit from . Uniformity is an additional requirement. The hardwired unary example makes the distinction concrete.
Common mistake
(Reading a count without its variable list)
Quoting "the number of satisfying assignments of " without naming the variable list is incomplete, because unused variables each double the count. Comparing counts of two formulas is meaningful only on a common list, or after dividing by to obtain the density.
Practice and solutions
Quick check
(How many satisfying assignments does have on the variable list ?)
Count the assignments that fail.
Solution · Answer
Three: all assignments except satisfy the formula.
Quick check
(Why does a polynomial-size circuit family not necessarily decide a language by a Turing machine?)
Ask what the definition says about the map from to .
Solution · Answer
The definition places no computability requirement on the map from to . The family may hardwire an undecidable sequence of bits, as in the unary example.
Quick check
(Compute of on the list using the multiplicativity proposition.)
Check first that the two conjuncts use disjoint variables.
Solution · Answer
The formulas (variables ) and (variable ) are variable-disjoint. The count of is and the count of is , so the product is . Directly: is forced and , giving assignments.
Quick check
(A formula has satisfying assignments on a list of variables. What are its count and density after appending unused variables?)
Each satisfying assignment extends in ways.
Solution · Answer
The new count is on variables. The density before is and after is , unchanged.
Quick check
(Show that if then its complement also lies in .)
Modify each circuit slightly.
Solution · Answer
Given circuits of size at most for , form by adding one NOT gate after the output of . It has at most gates, still polynomial, and exactly when for of length . Note that no uniformity is needed or used.