I came across following problem:
Which of the following problems is/are P-problems?
(I) Equivalence of DFA's
(II) Equivalence of NFA
(III) Equivalence of regular expressions
Now I know I there exist neat algorithm to find whether given two DFAs are equivalent or not. So (I) must be P-problem. I am doubtful about (II) and (III). There is a procedure to convert every NFA to DFA. So to check whether equivalence of two NFAs, we can first covert them into DFAs and then check their equivalence in P-time. But seems that we cannot convert NFA to DFA in P-time, hence equivalence of NFA seems not a P-problem. Same for (III). Am I correct with this?