1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ Have you tried proving either claim? $\endgroup$
    – Raphael
    Commented Apr 18, 2019 at 22:10

1 Answer 1

Reset to default
4
$\begingroup$

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.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ You need a $\Theta$ there. ;) $\endgroup$
    – Raphael
    Commented Apr 18, 2019 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
    Commented Apr 18, 2019 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
    Commented Apr 19, 2019 at 9:23

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.