Deciding DFA-Primality Is NP-Hard

We denote the propositional logic satisfiability problem for formulas in conjunctive normal form (CNF) by CNFSAT. It is well known that CNFSAT is NP-complete [2]. From here on, we call propositional logic formulas in CNF simply CNF-formulas.

As mentioned, we prove Theorem 3.1 by a reduction from CNFSAT. For a given CNF-formula $\mathrm{\Phi }$, the reduction yields a CNF-DFA ${𝒜}_{\mathrm{\Phi }}$ so that $\mathrm{\Phi }$ is satisfiable if and only if ${𝒜}_{\mathrm{\Phi }}$ is prime.

Before we can describe the reduction, we have to fix some notation. For the remainder of Section 3, let $X=\{x_1,\mathrm{\dots },x_r\}$ be a set of $r\in {\mathbb{N}}_{\ge 1}$ numbered variables, and let $\mathrm{\Phi }$ be a CNF-formula over $X$. W.l.o.g. we assume that $\mathrm{\Phi }$ has at least one clause and that every variable appears at most once in every clause.

To simplify the construction of ${𝒜}_{\mathrm{\Phi }}$, we fix a special notation for $\mathrm{\Phi }$. Namely, we write $\mathrm{\Phi }=(e_1^1\vee \mathrm{\cdots }\vee e_r^1)\wedge \mathrm{\cdots }\wedge (e_1^s\vee \mathrm{\cdots }\vee e_r^s)$, where $s\in {\mathbb{N}}_{\ge 1}$ is the number of clauses of $\mathrm{\Phi }$, and $e_i^k\in \{\neg x_i,x_i,\perp \}$ is the $i$-th element in the $k$-th clause where $k\in \{1,\mathrm{\dots },s\},i\in \{1,\mathrm{\dots },r\}$. In other words, in our notation, every clause has exactly $r$ elements and the $i$-th element of every clause is either a literal of the $i$-th variable $x_i$ or $\perp$. Here, $\perp$ is a special symbol that always evaluates to False. It is easy to see that $\mathrm{\Phi }$ can be written in this way.

Towards the definition of ${𝒜}_{\mathrm{\Phi }}$, we introduce some additional notation. Let $\mathrm{\Sigma }=\{0,1,c,d\}$. We call a string $u\in {\{0,1\}}^r$ an assignment string. As usual, an assignment over $X$ is a function $\gamma :X\to \{0,1\}$. An assignment $\gamma$ over $X$ induces an assignment string $u_{\gamma }\in {\{0,1\}}^r$ in the following way: $u_{\gamma }=\gamma (x_1)\mathrm{\dots }\gamma (x_r)$. Conversely, an assignment string $u={\sigma }_1\mathrm{\dots }{\sigma }_r\in {\{0,1\}}^r$ induces an assignment ${\gamma }_u$ over $X$ in the following way: ${\gamma }_u(x_i)={\sigma }_i$ for all $i\in \{1,\mathrm{\dots },r\}$.

Now we can consider the reduction, that is, the construction of the CNF-DFA ${𝒜}_{\mathrm{\Phi }}=(Q_{\mathrm{\Phi }},\mathrm{\Sigma },p_0,{\delta }_{\mathrm{\Phi }},F_{\mathrm{\Phi }})$ out of the given CNF-formula $\mathrm{\Phi }$. The CNF-DFA ${𝒜}_{\mathrm{\Phi }}$ is outlined in Figure 1. It is formally defined in the full version [11, Definition A.1]. The key property of ${𝒜}_{\mathrm{\Phi }}$ that we want to prove is formalized as:

As mentioned above, the compositionality of ${𝒜}_{\mathrm{\Phi }}$ depends solely on the max-visiting words of ${𝒜}_{\mathrm{\Phi }}$. We will discuss this in Section 3.2.1. For now, we will focus on the design of ${𝒜}_{\mathrm{\Phi }}$ and give an intuition for it.

The CNF-DFA ${𝒜}_{\mathrm{\Phi }}$ consists of two devices, the assignment device and the formula device. The assignment device consists of the states $p_0,\mathrm{\dots },p_r$ and $p_c^0$. To fully traverse the assignment device, that is, to start in $p_0$ and reach $p_c^0$, a string $ud$ with $u\in {\{0,1\}}^r$ has to be read. Therefore, the assignment device enforces that every max-visiting word is prefixed by an assignment string $u\in {\{0,1\}}^r$ (followed by a single $d$). Subsequently, the assignment string $u$ is interpreted as the assignment ${\gamma }_u$ for $\mathrm{\Phi }$ which it induces.

The formula device consists of $s$ clause rows. For $k\in \{1,\mathrm{\dots },s\}$, the $k$-th clause row encodes the $k$-th clause of $\mathrm{\Phi }$, that is, $(e_1^k\vee \mathrm{\cdots }\vee e_r^k)$. Thus, the formula device in its entirety encodes all clauses and thereby $\mathrm{\Phi }$. The $k$-th clause row consists of the states $p_1^k,{\widehat{p}}_1^k,\mathrm{\dots },p_r^k,{\widehat{p}}_r^k$ and $p_c^k$. Among these, ${\widehat{p}}_r^k$ is the positive target state of the $k$-th clause row, which is also the designated entry point for the subsequent clause row. And further, $p_r^k$ is the negative target state of the $k$-th clause row, which prevents ${𝒜}_{\mathrm{\Phi }}$ from entering the subsequent clause row.

We point out that $p_r$ is part of the assignment device enforcing the prefix $ud$, but also functions similarly to a positive target state for letters $0$ and $1$. In particular, it is the designated entry point for the first clause row. Therefore, we denote the state $p_r$ also by ${\widehat{p}}_r^0$.

The formula device is designed to enforce two assertions.

Firstly, every max-visiting word of ${𝒜}_{\mathrm{\Phi }}$ is of the form $ud{c}^{\mu }$, where $u\in {\{0,1\}}^r$ is an assignment string and $\mu$ depends on $|\mathrm{\Phi }|$. To be precise, this first assertion is enforced by the two devices together: The assignment device enforces the prefix $ud$ and the formula device the suffix $c^{\mu }$. The first assertion is formalized further below in Lemma 3.11 (i).

Secondly, if ${\gamma }_u$ satisfies the $k$-th clause, then $u$ induces a run from the positive target state ${\widehat{p}}_r^{k-1}$ of the $(k-1)$-th clause to the positive target state ${\widehat{p}}_r^k$ of the $k$-th clause. Else, $u$ induces a run from the positive target state ${\widehat{p}}_r^{k-1}$ of the $(k-1)$-th clause to the negative target state $p_r^k$ of the $k$-th clause. The second assertion is formalized in:

Note that reading $0$ or $1$ in any negative target state $p_r^k$ leads to $p_{-}$, while reading $0$ or $1$ in the final positive target state ${\widehat{p}}_r^s$ leads to $p_{+}$. Together with the second assertion enforced by the formula device, this implies that, for every $l\ge s+2$, a word of the form $u^{l}d{c}^{\mu }$ is accepted by ${𝒜}_{\mathrm{\Phi }}$ if and only if ${\gamma }_u$ satisfies $\mathrm{\Phi }$. We expand on this argument in our discussion of Lemma 3.12 in Section 3.2.2. Also in Section 3.2.2, we will see that ${𝒜}_{\mathrm{\Phi }}$ is prime if and only if ${𝒜}_{\mathrm{\Phi }}$ accepts some word of the form $u^{l}d{c}^{\mu }$. Thus, ${𝒜}_{\mathrm{\Phi }}$ is prime if and only if $\mathrm{\Phi }$ is satisfiable.

We have outlined the CNF-DFA ${𝒜}_{\mathrm{\Phi }}$ yielded by the reduction and given an intuition for its design. Next, we prove the correctness of the reduction.

We complete the proof of Theorem 3.1 by proving the correctness of the reduction. That is, we prove Lemma 3.2, that $\mathrm{\Phi }$ is satisfiable if and only if ${𝒜}_{\mathrm{\Phi }}$ is prime. We accomplish this in two steps. In Section 3.2.1, we characterize the compositionality of CNF-DFAs. Then in Section 3.2.2, we exploit this characterization to prove Lemma 3.2 and thereby Theorem 3.1.

In Sections 3.1 and 3.2, we improved the lower complexity bound of the general problem Prime-DFA. Now we conclude Section 3 by arguing that this improved lower bound is tight for the restriction of Prime-DFA to minimal linear safety ${\text{ADFA}}^{+}$s.

We denote the restriction of Prime-DFA to DFAs whose respective minimal DFA is a minimal linear safety ${\text{ADFA}}^{+}$ by ${\text{Prime-}\text{S}\text{ADFA}}^{+}$.

The restriction of Prime-DFA to ADFAs, so to truly acyclic DFAs, was studied in [10]. Motivated by this, we study ${\text{Prime-}\text{S}\text{ADFA}}^{+}$. For a comparison of the compositionality of ADFAs and ${\text{ADFA}}^{+}$s, we refer to Section 4.1. Here, we prove:

We proved Theorem 3.1, the NP-hardness of Prime-DFA, by a reduction from CNFSAT. At the heart of this reduction was the construction of the CNF-DFA ${𝒜}_{\mathrm{\Phi }}$ out of the given CNF-formula $\mathrm{\Phi }$. With Lemma 3.5, every CNF-DFA is also a minimal linear safety ${\text{ADFA}}^{+}$. Thus, we immediately get:

To arrive at Theorem 3.13, we additionally prove:

To prove that ${\text{Prime-}\text{S}\text{ADFA}}^{+}$ is in NP, we describe a guess-and-verify NP-algorithm for ${\text{Prime-}\text{S}\text{ADFA}}^{+}$ which exploits Theorem 3.9. Given a minimal linear safety ${\text{ADFA}}^{+}$ $𝒜$, the algorithm guesses a max-visiting word $w\in 𝒦(𝒜)$ and then verifies that $w$ breaks the mp-prop, meaning that $w$ witnesses that $𝒜$ does not have the mp-prop. To do so, it simulates the initial run of $𝒜$ on $w[i,j;l]$ for every pair and every relevant $l$. The key insight here is that, for every such pair $i,j$, there is a polynomially bounded value $l_{i,j}^{\prime }$ such that only the values $l\le l_{i,j}^{\prime }$ are relevant. Thus, the algorithm has to simulate only polynomially many runs. If the algorithm finds that $w$ indeed breaks the mp-prop, it accepts. Else, it rejects.

The polynomial runtime of the algorithm follows immediately from the key insight just mentioned. The runtime is dominated by the simulation of the runs. There are only polynomially many pairs $i,j$. And for each pair, there are only polynomially many relevant pumpings $w[i,j;l]$, each having polynomial length. Thus, the algorithm has polynomial runtime.

Regarding the correctness, if $𝒜$ is prime, then there is a word breaking the mp-prop. The algorithm guesses this word and subsequently accepts. Else, that is, if $𝒜$ is composite, then no word breaking the mp-prop exists. Thus, the algorithm is forced to reject no matter which word it guesses. In total, the algorithm works correctly for ${\text{Prime-}\text{S}\text{ADFA}}^{+}$.

To summarize, we have described an NP-algorithm for ${\text{Prime-}\text{S}\text{ADFA}}^{+}$. Thus, we have proven Lemma 3.15. Together with the already established Lemma 3.14, we immediately get Theorem 3.13, the NP-completeness of ${\text{Prime-}\text{S}\text{ADFA}}^{+}$.

We denote the restriction of Prime-DFA to DFAs deciding a finite language by${\text{Prime-DFA}}_{\text{fin}}$. Note that a DFA decides a finite language if and only if its minimal DFA is an ADFA. Thus, the problems ${\text{Prime-DFA}}_{\text{fin}}$ and ${\text{Prime-}\text{S}\text{ADFA}}^{+}$ are very similar: ${\text{Prime-DFA}}_{\text{fin}}$ considers ADFAs, so truly acyclic DFAs, while ${\text{Prime-}\text{S}\text{ADFA}}^{+}$ considers ${\text{ADFA}}^{+}$s, so “almost” acyclic DFAs possessing an accepting sink.

In this paper, we have proven that ${\text{Prime-}\text{S}\text{ADFA}}^{+}$ is NP-complete. With [10, Theorem 4.1], ${\text{Prime-DFA}}_{\text{fin}}$ is NL-complete. Therefore, the simple addition of an accepting sink leads to a jump in the complexity of the primality problem (assuming $\text{NL}\subset \text{NP}$). We give an intuition for this somewhat surprising fact.

The reduction from CNFSAT crucially hinges on the fact that the CNF-DFA ${𝒜}_{\mathrm{\Phi }}$ can potentially enter the accepting sink after reading the prefix $u^{s+2}$ of $w[1,r+1;s+2]$, where $w=ud{c}^{\mu }\in 𝒦({𝒜}_{\mathrm{\Phi }})$ is a max-visiting word. In other words, it can enter the accepting sink after “pumping up” $w$ so that the assignment string $u$ is checked against every clause row. Once in the accepting sink, the suffix $d{c}^{\mu }$ of dummy letters can be read and the pumping $w[1,r+1;s+2]$ is accepted.

No construction of this kind is possible for ADFAs. Every ADFA has a threshold value so that it rejects every word longer than that threshold value. This is obvious, because for words longer than the threshold value, it runs out of non-sinks and necessarily enters the rejecting sink. Therefore, “pumping up” and thereby lengthening the ADFA-equivalent of a max-visiting word necessarily leads to an overlong word that is rejected.

Thus, with the existence of an accepting sink, no threshold value exists so that words longer than that threshold value are rejected. This simple additional complication is enough to lead to the jump in complexity, from NL-completeness for ${\text{Prime-DFA}}_{\text{fin}}$ to NP-completeness for ${\text{Prime-}\text{S}\text{ADFA}}^{+}$.

With ˜2.1, we followed [8] and defined compositionality using the index of the given DFA. However, without stating so explicitly, [6, 7] employed a slightly different definition, using the size instead of the index. In [10], this difference was made explicit by introducing the notion of S-compositionality and the respective decision problem. We follow [10] and define:

We denote the problem of deciding S-primality for a given DFA by S-Prime-DFA.

Many results known for compositionality carry over trivially to S-compositionality. In particular, Prime-DFA is in ExpSpace [8, Theorem 2.4]. The proof of this result has to be adapted only slightly to prove that S-Prime-DFA is in ExpSpace as well [10, Theorem 6.3].

However, the NL-hardness of Prime-DFA, established in [8, Theorem 2.5], does not carry over trivially to S-Prime-DFA. The NL-hardness of S-Prime-DFA is established in [10, Theorem 6.3] by using a reduction of a different problem than the one used for Prime-DFA.

Here, we highlight that the improved lower complexity bound of Prime-DFA does carry over trivially to S-Prime-DFA. We established the NP-hardness of Prime-DFA by a reduction from CNFSAT. The CNF-DFAs yielded by this reduction are minimal. Thus, with the same reduction, we get:

Indeed, it is well known that DFA minimization can be done in polytime. Thus, by making the transition from NL-hardness to NP-hardness, the distinction between compositionality and S-compositionality loses its edge because we can always minimize the given DFA. This simple argument is an alternative way to arrive at Theorem 4.2.