# Why are those very similar languages in a different complexity class?

i am having a real time understand why the following two languages are in two different complexity classes(the first is NP-Hard and the second is in P). tried to look online at various resources and lecture notes/books, but couldn't find a reason for it. the languages are:

1.$$NONEMPTY-INTER_{DFA}\:=\:\left\{ |\:A_1,...,A_k\:are\:DFAS\:and\:L\left(A_1\right)\cap...\:\cap L\left(A_k\right)\:\ne \varnothing \right\}$$

2.$$NONDISJOINT_{DFA}\:=\:\left\{ |\:A\:and\:B\:are\:DFAS\:and\:L\left(A\right)\:\cap L\left(b\right)\:\ne \varnothing \right\}$$

why is the second can be run in a polynomial time on a turing machine, and the first can not? would really appreciate an explanation for this.

• Have you tried proving either claim? Apr 18, 2019 at 22:10

It's because the running time to test $$k$$ DFAs, each of size $$n$$, is something like $$\Theta(n^k)$$. This is polynomial when $$k$$ is fixed (like 2), but exponential when $$k$$ is not fixed (e.g., when $$k=n$$, you get something like $$n^n$$).
• You need a $\Theta$ there. ;) Apr 18, 2019 at 22:10