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> |\: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,B> |\: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.

  • $\begingroup$ Have you tried proving either claim? $\endgroup$ – 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.)

| cite | improve this answer | |
  • $\begingroup$ You need a $\Theta$ there. ;) $\endgroup$ – Raphael Apr 18 '19 at 22:10
  • $\begingroup$ @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. $\endgroup$ – Evil Apr 18 '19 at 23:04
  • 1
    $\begingroup$ @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. $\endgroup$ – Raphael Apr 19 '19 at 9:23
  • $\begingroup$ Ok. Thanks Raphael. $\endgroup$ – Evil Apr 19 '19 at 10:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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