1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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

    -Job-

    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook