Ace Academy Test series

Question

Answer 1

Minimizing $2$ DFA's can be done in $O(n log n)$ time using Hopcroft's algorithm.

So there exists a polynomial time algorithm to do so but

For a given NFA of n state, number of states in equivalent DFA is atmost $2^n$.

Worst case complexity is $O(2^n)$

Hence B is not a P problem

Similarly comparing 2 regex will require to first convert both regex to NFA and then to DFA which will also not take polynomial time

So $A$ is correct answer

Comments

p and np concept is in syllabus ???

---

Deepanshu some say it is, some say its not

don't know :p