Results 1 to 10 of 10

Math Help - NP-Complete question

  1. #1
    Newbie
    Joined
    Dec 2011
    Posts
    16

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2011
    Posts
    16

    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2011
    Posts
    127

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: NP-Complete question

    Quote Originally Posted by complexity9 View Post
    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).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Dec 2011
    Posts
    16

    Re: NP-Complete question

    Quote Originally Posted by emakarov View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Dec 2011
    Posts
    16

    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!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: NP-Complete question

    Quote Originally Posted by complexity9 View Post
    By the way, the Lewis and Papadimitriou book you are referring to, which edition do you have?
    I have second edition.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Dec 2011
    Posts
    16

    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!
    Last edited by complexity9; December 7th 2011 at 10:47 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 8
    Last Post: December 7th 2011, 04:23 PM
  2. How I complete this question ..
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: February 14th 2010, 07:56 AM
  3. I want to complete my answer in this question
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: December 23rd 2009, 07:09 AM
  4. Complete Interval of Convergence Question(s)
    Posted in the Calculus Forum
    Replies: 10
    Last Post: April 16th 2008, 08:03 PM
  5. complete matrices question
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: June 30th 2007, 07:01 PM

/mathhelpforum @mathhelpforum