Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

NP-Complete question

  1. Dec 5, 2011 #1
    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. jcsd
  3. Dec 6, 2011 #2


    User Avatar
    Science Advisor

    Consider an instance of SAT - you're given a specific boolean formula and are asked whether a variable assignment exists that evaluates to true.

    How many such possible assignments are there, for a specific SAT instance? You might say that each SAT instance itself has a language: the language composed of all distinct variable assignments that evaluate to true.

    Additionally, under this interpretation, all unsatisfiable SAT instances have the same language - an empty language - given that there are no assignments that evaluate to true.

    Do you see a way to solve SAT by using a solution to the problem of determining whether two NFAs have the same language?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook