{\huge Counting Is Sometimes Easy}

A case where we can count objects in polynomial time \vspace{.3in}

Mike Sipser is one of the top theorists, especially in the area of complexity theory. He is long known for some very clever proofs and his famous survey paper on the status of $latex {\mathsf{P = NP}}&fg=000000$. He is recently known for co-authoring the paper that introduced adiabatic quantum computing, which is the kind being given physical realization by the company D-Wave Systems. But he is perhaps best known nowadays for his textbook Introduction to the Theory of Computation. I have used the earlier version many times for teaching our undergraduate class; I have not used the third edition, mainly because I teach other things these days.

Today I want to talk about a topic that is covered in his book, finite state automata.

Yes, lowly finite state automata (FSA). In my opinion FSA are one of the great inventions of theory. They led Michael Rabin and Dana Scott to discover nondeterminism, yielding a Turing Award along the way. They led algorithm designers like Don Knuth to discover, with Jim Morris and Vaughan Pratt, the first linear-time pattern matching algorithm. And much more.

Mike's book was discussed before here, where I talked about his use of FSA to prove that the first order theory of addition is decidable. This is one of my favorite applications of FSA, which I learned from Ann Yasuhara directly---it is also included in her early book, Recursive Function Theory and Logic.

A Look at the Book

Mike's book proves some interesting theorems that are ancient---okay, many decades old. This yields some strange omissions, which are bound up with the history of the theorems. For example, consider the following classic one:

Theorem 1 A language is context-free if and only if some nondeterministic pushdown automaton (PDA) accepts it.

This is proved in detail in his book---see page 117 in the new edition, Theorem 2.20. But the proof establishes more, much more. I have used both of these consequences in my own work over the years.

• Given a context-free grammar we can construct the PDA in polynomial time, and conversely given the PDA we can construct the grammar.
• The sizes of the grammar and the description of the PDA are related by a polynomial bound.

Note that the best construction, I believe, goes from a PDA with $latex {S}&fg=000000$ states to a grammar with $latex {O(S^{3})}&fg=000000$ rules. If there is a better one it would have some interesting consequences.

Let me say that this omission is not isolated to Mike's book, but others most always leave out these interesting refinements. I believe that the reason is simple: the above theorem was proved before polynomial time was defined, and the textbook is sequenced that way. Hence the omission. Perhaps they can be added to a fourth edition.

Ken adds---writing most of the rest of this post:I now like the sequence of skipping grammars and PDA's and going straight from regular languages and FSA to Turing computability and complexity. After this 'kernel' material the instructor has an option of covering grammars, and then the polynomial-overhead concepts are in place. Or the instructor can do more with complexity or logic or some other core topic.

Counting

Let's get back to FSA and counting.

Theorem 2 Let $latex {M}&fg=000000$ be a deterministic FSA with $latex {S}&fg=000000$ states and input alphabet $latex {\Sigma}&fg=000000$. Then we can determine the cardinality $latex {C_m(n)}&fg=000000$ of the set $latex {L(M)\cap \Sigma^{n}}&fg=000000$ in time polynomial in $latex {S}&fg=000000$ and $latex {n}&fg=000000$.

Put another way, we can count in polynomial time the number of strings of length $latex {n}&fg=000000$ that a FSA accepts. If the FSA is fixed, then the time is polynomial only in $latex {n}&fg=000000$. Actually, in this case the time is essentially bi-linear in $latex {S}&fg=000000$ and $latex {n}&fg=000000$---it depends on the exact computational model.

The algorithm to prove this is often described as ``dynamic programming,'' but often that just means maintaining a well-chosen data structure. Here we allocate a slot for each state $latex {q}&fg=000000$ of the FSA, and maintain for each $latex {k \leq n}&fg=000000$ the number $latex {N_{k,q}}&fg=000000$ of strings of length exactly $latex {k}&fg=000000$ that reach $latex {q}&fg=000000$ from the start state $latex {s}&fg=000000$. Initially $latex {k = 0}&fg=000000$, $latex {N_{0,s} = 1}&fg=000000$ for the empty string, and all other $latex {N_{0,q} = 0}&fg=000000$. Now to update it to $latex {N_{k+1,q}}&fg=000000$, find all states $latex {p}&fg=000000$ and characters $latex {c}&fg=000000$ such that $latex {\delta(p,c) = q}&fg=000000$, where $latex {\delta}&fg=000000$ is the transition function of $latex {M}&fg=000000$, and sum up $latex {N_{k,p}}&fg=000000$. That is,

$latex \displaystyle N_{k+1,q} = \sum_{p,c: \delta(p,c) = q} N_{k,p}. &fg=000000$

Sounds simple, but as often happens in complexity, delicacy and difficulty lurk not too far away.

The NFA Case and an Application

First, does the algorithm work when $latex {M}&fg=000000$ is nondeterministic? It certainly runs, and counts something, but not the number of accepted strings. So can we modify it to do so?

The answer is no---or maybe better to say ``ostensibly not'': Given a Boolean formula that is a conjunction of clauses $latex {C_1,\dots,C_m}&fg=000000$, design an NFA $latex {M}&fg=000000$ that begins with a nondeterministic choice of one of $latex {m}&fg=000000$ states $latex {q_j}&fg=000000$. From every $latex {q_j}&fg=000000$, $latex {M}&fg=000000$ starts reading its input $latex {x \in \{0,1\}^n}&fg=000000$ deterministically. The part of $latex {M}&fg=000000$'s code from $latex {q_j}&fg=000000$ is written so that if $latex {x}&fg=000000$ is an assignment that makes every literal in $latex {C_j}&fg=000000$ false---note that the literals can be presented in index order---then $latex {M}&fg=000000$ accepts $latex {x}&fg=000000$. Thus the formula is un\/satisfiable if and only if $latex {C_M(n) = 2^n}&fg=000000$. So if we had a $latex {\mathsf{poly}(Sn)}&fg=000000$ algorithm to compute $latex {C_M(n)}&fg=000000$, we'd have $latex {\mathsf{NP = P}}&fg=000000$.

Moreover, $latex {2^n - C_M(n)}&fg=000000$ counts the satisfying assignments. Hence relaxing $latex {M}&fg=000000$ from DFA to NFA makes our little problem $latex {\mathsf{\#P}}&fg=000000$-complete. Now it's important that $latex {M}&fg=000000$ is part of the input. If $latex {M}&fg=000000$ is fixed and we only want to compute $latex {C_M(n)}&fg=000000$ given $latex {n}&fg=000000$, then of course we can convert $latex {M}&fg=000000$ to an equivalent DFA which is likewise fixed, and run our algorithm. Hence one must be delicate with what constitutes the input.

For an example, call a string special if it contains $latex {j}&fg=000000$ copies of the pattern $latex {u = 010111}&fg=000000$ for some $latex {j}&fg=000000$ that is a prime number. We can count the number of special strings of length $latex {n}&fg=000000$ in time polynomial in $latex {n}&fg=000000$. To do so, we take $latex {m = \lfloor n/6 \rfloor}&fg=000000$ and program a choice over all $latex {j \leq m}&fg=000000$ as before, this time keeping only the $latex {q_j}&fg=000000$ for which $latex {j}&fg=000000$ is prime. From each $latex {q_j}&fg=000000$ we program a DFA $latex {M_j}&fg=000000$ that accepts a string $latex {x}&fg=000000$ if and only if it contains exactly $latex {j}&fg=000000$ copies of $latex {u}&fg=000000$. This resembles the $latex {\mathsf{SAT}}&fg=000000$ case, but is different because there is no overlap in the strings accepted by the respective $latex {M_j}&fg=000000$. Hence we just count the numbers of length-$latex {n}&fg=000000$ strings accepted by each and add them up.

This is not a hugely important application. We selected it to show that there are counting problems that might be tricky to solve without the FSA method. This and other examples may be useful.

What Else Can Be Counted?

Also note that even though $latex {\mathsf{2SAT}}&fg=000000$ is in $latex {\mathsf{P}}&fg=000000$, the counting problem $latex {\mathsf{\#2SAT}}&fg=000000$ is still $latex {\mathsf{\#P}}&fg=000000$-complete. For an aside, $latex {\mathsf{2SAT}}&fg=000000$ is a major example in Mike's quantum paper, but here we raise the question, what else can be counted?

For instance, counting the number $latex {N_m(f)}&fg=000000$ of solutions to an $latex {n}&fg=000000$-variable polynomial $latex {f}&fg=000000$ over $latex {\mathbb{Z}_m}&fg=000000$ is $latex {\mathsf{\#P}}&fg=000000$-complete. It becomes $latex {n^{O(1)}}&fg=000000$-time, however, when $latex {f}&fg=000000$ has degree at most $latex {2}&fg=000000$. This is when $latex {m}&fg=000000$ is fixed. What if $latex {m}&fg=000000$ is variable? We can also ask about computing $latex {N_m(f - j)}&fg=000000$ for all $latex {j \in \mathbb{Z}_m}&fg=000000$, for the particular purpose of computing the exponential sum

$latex \displaystyle Z_f = \sum_{j=0}^{m-1} N_m(f - j) \omega^j = \sum_{x \in \mathbb{Z}_m^n} \omega^{f(x)}, &fg=000000$

Dick co-authored a paper recently with Jin-Yi Cai, Xi Chen, and Pinyan Lu, showing that when $latex {f}&fg=000000$ has degree at most $latex {2}&fg=000000$, $latex {Z_f}&fg=000000$ is computable in time polynomial in $latex {n}&fg=000000$ and $latex {\log m}&fg=000000$. In particular this means that for $latex {m = 2^r}&fg=000000$, when we can represent the members of $latex {\mathbb{Z}_m}&fg=000000$ by strings in $latex {\{0,1\}^r}&fg=000000$, the time to compute $latex {Z_f}&fg=000000$ is $latex {\mathsf{poly}(nr)}&fg=000000$.

A little thought shows that this suffices to compute any individual number $latex {N_m(f - j)}&fg=000000$ in time $latex {\mathsf{poly}(nm)}&fg=000000$, indeed by computing all of them. But if we just want one, and $latex {m = 2^r}&fg=000000$, can we do it in time $latex {\mathsf{poly}(nr)}&fg=000000$? This is not obvious to me (Ken), and at least for now leaves the funny situation where we can compute in $latex {\mathsf{poly}(nr)}&fg=000000$ time the historically important $latex {Z_f}&fg=000000$ function which involves all the $latex {N_m(f - j)}&fg=000000$ values, but don't see a way to compute any one of them in the same time.

Open Problems

Whose originally proved efficient counting for deterministic FSA? We seem to not be able to track that down. Are there some cool applications?

What is the answer to the last problem? Should counting receive more emphasis in texts at the level of Mike's?