1. ## NP-Complete question

An NFA (nondeterministic finite automaton) is acyclic if there is no path from a state to itself.

Decision problem: Given two acyclic NFAs A and B, does L(A)=L(B), i.e. does A accept the same language as B.

Show that the above decision problem is NP-Complete.

I am unable to show that it is either NP or NP-hard, but was told that we may use a reduction from SAT to show NP-Hardness. Any help would be appreciated, I have been thinking about this for a while and don't know where to start!

2. ## Re: NP-Complete question

In fact, it is the complement of the equivalence problem, i.e., the problem whether two given acyclic NFAs are inequivalent, that is NP-complete. This is described in the "Elements of the Theory of Computation" by Lewis and Papadimitriou, second edition. The inequivalence problem for *-free regular expressions is proved to be NP-complete in theorem 7.3.8, and the NP-completeness of the corresponding problem for acyclic NFAs is given as problem 7.3.7.

The certificate of inequivalence for NFAs $A_1$ and $A_2$ is a string from $(L(A_1)-L(A_2))\cup(L(A_2)-L(A_1))$. Since the automata are acyclic, the length of words they accept does not exceed the number of states.

To prove that inequivalence of NFAs is NP-hard, we can reduce SAT to inequivalence of *-free regular expressions and then to that of automata. As described in p. 103 of the book, converting a regular expression into an equivalent NFA takes polynomial time (this is seen by examining the proof of the theorem about the equivalence of regular expressions and NFAs). One needs to make sure that *-free expressions produce acyclic automata.

The idea of the reduction of SAT is the following. Given a Boolean formula $C_1\land\dots\land C_m$ in CNF, generate two regular expressions $\alpha_1\cup\dots\cup\alpha_m$ and $(0\cup1)\dots(0\cup1)$. If the Boolean formula has $n$ variables, then $\alpha_i=\alpha_{i1}\dots\alpha_{in}$ where

$\alpha_{ij}=\begin{cases}0&\text{if }x_j\text{ is a literal of }C_i}\\1&\text{if }\bar{x}_j\text{ is a literal of }C_i}\\0\cup1&\text{otherwise}\end{cases}$

Then $L(\alpha_i)$ is the set of all truth assignments that fail to satisfy $C_i$, so $L(\alpha_1\cup\dots\cup\alpha_m)$ is the set of assignments that make the Boolean formula false.

3. ## Re: NP-Complete question

Alright, I now understand how to show that the inequivalence decision problem is NP-hard. However, I'm not convinced about your argument as to why it is in NP:

I agree that the words that they accept can't exceed the number of states, but can't this still lead to an exponential blow-up of the search space. For example, if we have states {1,..,n}. Let state 1 have transitions to all the states in {2,...,n}. Similarly, let state k have transitions to all the states in {k+1, k+2, ..., n}. Then the number of possible paths is n! (n factorial), which is not polynomial-time (exponential).

Please let me know what you think of my argument above.

Cheers!

4. ## Re: NP-Complete question

Do you understand what NP means? It means a decision problem class for nondeterministic turing machines in polynomial time. If you can build a NFSA where an oracle that magically tells you which path to follow would lead you to an accepting state, if one exists, and there is always at least one path to a non-accepting state when no such state exists, and each path takes no longer than polynomial time, you can reduce that NFSA to a nondeterministic turing machine.

So yeah, it's in NP.

5. ## Re: NP-Complete question

Originally Posted by complexity9
I agree that the words that they accept can't exceed the number of states, but can't this still lead to an exponential blow-up of the search space. For example, if we have states {1,..,n}. Let state 1 have transitions to all the states in {2,...,n}. Similarly, let state k have transitions to all the states in {k+1, k+2, ..., n}. Then the number of possible paths is n! (n factorial), which is not polynomial-time (exponential).
In fact, I believe the number of paths in this example is $2^n < n!$, but yes, it is exponential. However, since the number of states is just $n$, the subset construction, which is used to construct a DFA from an NFA but which computes the set of states at each step "on the fly," runs a word through a nondeterministic automaton in polynomial time.

To see this, let E(p) be the set of states reachable from p without reading any symbols, i.e., via transitions labeled by the empty string. Then E(p) is computed in polytime w.r.t. the total number $m$ of states. Indeed, we keep the current set of reachable states, initially {p}, and for each such state and for each applicable transition we add the new state to the set if it is not already there. The size of the set is <= m, the number of all transitions is <= m^2, and the number of iterations where a new state is added is <= m. (See p. 69 of Lewis and Papadimitriou.)

Now, given an input string $w$, we again keep the current set of reachable states S. Given the next symbol $a$ from $w$, we add {E(q) | (p, a, q) is a transition and p ∊ S} to S. The size of S is <= m, so the total time required is $O(m^k|w|)$ for some $k$. (See p. 106 of the book.)

As Annatala pointed out, even if we tried each of the paths through an NFA, guessing a string and then checking that it leads to a successful state can be done nondeterministically in polynomial time. This is equivalent to taking as a certificate not just an accepted string, but also the path that takes this string to a successful state. In contrast, if running a string through an NFA did not take deterministic polytime, it is not clear how to check that a string is not accepted; this problem is in co-NP (but since, in reality, it is in P, it is in NP as well).

6. ## Re: NP-Complete question

Originally Posted by emakarov
To see this, let E(p) be the set of states reachable from p without reading any symbols, i.e., via transitions labeled by the empty string. Then E(p) is computed in polytime w.r.t. the total number $m$ of states. Indeed, we keep the current set of reachable states, initially {p}, and for each such state and for each applicable transition we add the new state to the set if it is not already there. The size of the set is <= m, the number of all transitions is <= m^2, and the number of iterations where a new state is added is <= m. (See p. 69 of Lewis and Papadimitriou.)

Now, given an input string $w$, we again keep the current set of reachable states S. Given the next symbol $a$ from $w$, we add {E(q) | (p, a, q) is a transition and p ∊ S} to S. The size of S is <= m, so the total time required is $O(m^k|w|)$ for some $k$. (See p. 106 of the book.)
Where in the above construction have you used the fact that the NFA's are acyclic? It seems that this construction works for all NFA (cyclic as well) in polynomial-time if it does not use the fact that the NFA is acyclic.

Edit: Okay I believe |w| < m, since NFA is acyclic, which makes O(m^k |w|) polynomial in m. If the NFA's are cyclic, there may exists a word of length not polynomially-bounded in m, making the running time not polynomial in m. Is this argument correct?

7. ## Re: NP-Complete question

Okay I believe |w| < m, since NFA is acyclic, which makes O(m^k |w|) polynomial in m. If the NFA's are cyclic, there may exists a word of length not polynomially-bounded in m, making the running time not polynomial in m. Is this argument correct?
Yes. I believe that by running time you mean the time of the nondeterministic TM that guesses the certificate and then checks it.

The only place where acyclicity is used is to ensure that the certificate has polynomial length with respect to the problem size. It turns out that there are families of pairs of inequivalent NFAs (with cycles) that differ only in strings that are exponentially long in the size of automata (L & P, p. 329). As for checking whether a string is accepted by an NFA, it is always polynomial in the combined size of the string and the NFA, i.e., the language of triples (NFA1, NFA2, certificate) is polynomially decidable.

8. ## Re: NP-Complete question

Okay got that! Thanks alot emakarov and Annatala for your useful responses. By the way, the Lewis and Papadimitriou book you are referring to, which edition do you have? This is because I'm going to the library soon to get this book, but I want to make sure that your page reference matches the book I get. Thanks again!

9. ## Re: NP-Complete question

Originally Posted by complexity9
By the way, the Lewis and Papadimitriou book you are referring to, which edition do you have?
I have second edition.

10. ## Re: NP-Complete question

guys, can you have a look at my new threads when you have time. If are you able to help out that would be great!

Thanks again!