1
$\begingroup$

$B=\{\left<M_1,M_2,...,M_k\right>\text{ : Each $M_i$ is a DFA and all of the $M_i$ accept some common string.} \}$

I'm trying to show that B is NP-complete. I know I have to reduce it to another NP-complete problem, but I'm having a lot of trouble coming up with the algorithm that decides B.

I was thinking I could keep track of all the DFAs accepted by M1 and then check those in M2, any that accept there I'd feed to M3 and so on until I either ran through all the DFAs (accept) or ran out of accepted strings (reject). I'm not really convinced this runs in NP time though. How exactly do I prove that it does? Or is this a terrible algorithm?

Thank you!

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Your question is a very basic one. Since you did not include much of an attempt to solve it on your own, we have little to work with. Let me direct you towards our reference questions. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. $\endgroup$
    – D.W. ♦
    Commented Nov 25, 2015 at 2:20
  • 1
    $\begingroup$ Your paragraph beginning "I was thinking.." sounds confused about the difference between NP vs NP-complete; please see cs.stackexchange.com/q/9556/755. It also sounds like you are struggling to find a reduction; for that, please refer to cs.stackexchange.com/q/11209/755 and cs.stackexchange.com/q/1240/98. (possible dup? any community votes?) $\endgroup$
    – D.W. ♦
    Commented Nov 25, 2015 at 2:22
  • 1
    $\begingroup$ Hint: Reduce SAT to your problem. Let each $M_i$ be in charge of a specific clause of the input SAT instance. $\endgroup$
    – Yuval Filmus
    Commented Nov 25, 2015 at 8:16
  • $\begingroup$ To show that your problem is hard, you do not reduce it to a known hard problem, you reduce the known hard problem to your problem. Could you for example reduce 3SAT to your problem? That is you are given clauses and you could derive DFAs $M_1,...,M_k$ that have a common string iff the set of clauses are satisfiable? $\endgroup$
    – phs
    Commented Nov 25, 2015 at 11:22

1 Answer 1

Reset to default
3
$\begingroup$

Your problem is actually not NP-complete (unless NP=PSPACE), though it is NP-hard. The problem is that the witness - the string in the intersection - could be very long.

Kozen showed that DFA-intersection is PSPACE-complete, which implies the preceding paragraph. For a very similar proof (of a different statement), see my writeup.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.