# Prove L is NP-hard

I have no clue how to prove this question.

Consider the language

$L = \{ \langle D_1, D_2, ... ,D_K \rangle : k \in {N},$ the $D_i$ are DFAs and ${\bigcap}_{i=1}^k L(D_i) = \emptyset \}$

Prove that L is NP-hard.

Can someone guide me through this problem? I understand that I will have to reduce it into something, I just don't know what to reduce to.

• Hint: the intersection operation is very similar to the AND operation... taking the intersection of $k$ DFAs could be paralleled to taking the conjunction of $k$ boolean expressions. I haven't worked out the reduction in full, but it was the first thing I noticed when seeing the problem. I assume you're familiar with 3-SAT? – jmite Nov 26 '13 at 0:42
• Yes, that is the direction I am currently pursuing. But I wasn't sure whether I can get the expected proof. – vanblaze Nov 26 '13 at 1:38

1. You have to encode a truth assignment as a word. Say the word $\tt 101001001$ encodes $x_1=\text{TRUE}$, $x_2=\text{FALSE}$, and so on