# 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?
– Raphael
Apr 18 '19 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$$).

(We don't actually know for sure what the best running time for that is, but we suspect it's something like that; and that will explain why those similar-sounding problems have different complexity classes. Likewise, we don't actually know for sure that P is a different complexity class from NP, but we suspect it is.)

• You need a $\Theta$ there. ;)
– Raphael
Apr 18 '19 at 22:10
• @Raphael Theta here would mean that there doesn't exist algorithm that can test it faster, but it is possible to test in c*k time in the best case.
– Evil
Apr 18 '19 at 23:04
• @Evil No, it would mean that the problem space is truly that huge, preventing simple algorithms from working. D.W. says nothing about a complexity lower bound, which we don't know.
– Raphael
Apr 19 '19 at 9:23
• Ok. Thanks Raphael.
– Evil
Apr 19 '19 at 10:25