3
$\begingroup$

Almost the exact same question was asked here, but nobody proved or cited its #P-completeness! I found this question because I proved it is #P-complete (proof below), and the proof was trivial, but I couldn't find it anywhere on the web or in the discussion on that question! (One person commented "I suspect it is #P-complete".) So either my proof is wrong, which you can judge for yourself, or the result is novel, which I would think is highly unlikely. Which is it?


Proof:

Consider the set of regular expressions formed by the union and concatenation of symbols from $(\Sigma\cup{.})$, where $\Sigma$ is an alphabet and $.$ is a symbol for any $l\in\Sigma$. I will show that #SAT reduces in $O(mn)$ time to counting the number of strings that satisfy such a regex, where $m$ is the number of clauses and $n$ is the number of variables in the given formula $\varphi$.

The reduction is very simple. First, reduce #SAT to #UNSAT by noting that if $\varphi$ has $n$ variables, then $\#\text{SAT}(\varphi) = 2^n - \#\text{UNSAT}(\varphi)$. So now we have to count the number of falsifying assignments of the variables of $\varphi$.

To falsify $\varphi$, it suffices to falsify just one clause. We therefore want to find $$\left|\bigcup \limits_{C\in\varphi}F(C)\right|$$ where $F(C)$ is the set of assignments of literals that falsify $C$.

We thus write a regex representing the language of falsifying assignments for each clause. Using $\Sigma = \{0,1\}$, and letting $r_i$ be the $i^{th}$ symbol of a regex $r$, the regex for the language of assignments that falsify a clause $C$ is $$ r_i = \begin{cases} 0 & \text{if } x_i\in C \\ 1 & \text{if } \overline{x_i}\in C \\ . & \text{otherwise} \end{cases} $$

We then take the union of the regexes for each clause $C\in\varphi$. For example, if $\varphi = (x_1\vee \overline{x_2}\vee x_3) \wedge (x_1\vee x_3\vee \overline{x_4})\wedge (\overline{x_1}\vee \overline{x_4})$ we would have $r = $010.|0.01|1..1, where | denotes union.

The construction yields a union of $m$ strings, each of $n$ symbols. Thus the reduction takes $O(mn)$ time and the size of the regex-counting instance is polynomial in the size of the formula. Further, any regular expression that uses only concatenation, dot, and union represents a finite regular language (specifically, there is no Kleene star). So since we can solve #SAT by counting strings that satisfy such a regex, we can say that counting the words in a finite language is #P-complete.

$\endgroup$
  • $\begingroup$ "Almost the exact same question" they are very different. Your languages are finite. $\endgroup$ – Chao Xu Sep 8 '15 at 7:38
  • 4
    $\begingroup$ @ChaoXu: but if it is #P-complete for finite languages, then the problem "Given an NFA, count the number of matching words of length $k$" (the linked problem) is #P-complete when $k$ is given in unary ... so the two questions are not so different. However it seems a known result (see for example: dl.acm.org/citation.cfm?id=313803). Note that the problem is in P for deterministic finite automata. $\endgroup$ – Marzio De Biasi Sep 8 '15 at 11:14
  • $\begingroup$ @ChaoXu: How? I actually spent awhile thinking about this issue before Marzio's comment which is (I think) completely right. $\endgroup$ – Huck Bennett Sep 8 '15 at 18:10
  • $\begingroup$ @ChaoXu its equivalent, just take $n$ larger than the largest word in the language. In my problem $n$ is known as the number of variables of $\varphi$. $\endgroup$ – Elliot Gorokhovsky Sep 8 '15 at 18:13
  • 1
    $\begingroup$ It's also interesting to look at the problem "Given an NFA, count the number of matching words of length $k$" when k is given in binary. This problem is PSPACE-hard. I say this based on the proof that deciding equivalence of two regular expressions is PSPACE-hard. In that reduction, one reg-ex was constructed to accept all strings, and the other to accept all strings that are not valid rejecting computation histories of PSPACE machine M on input w. Using that second regular expression and taking $k$ to be the length of a computation history of M on w makes this other problem PSPACE-hard too. $\endgroup$ – Mikhail Rudoy Dec 30 '16 at 3:51
7
$\begingroup$

See this paper: Counting the size of regular sequences of given length is #P-complete: S. Kannan, Z. Sweedyk, and S. R. Mahaney. Counting and random generation of strings in regular languages. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 551–557, 1995.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.