Whether equivalence of different types of automata is of P-type?

Question

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?

Answer 1

The short answer to your question is that 1 is in P, and for 2 and 3 we don't know, but we strongly suspect that they are not in P.

In more detail, as you point out, checking whether two DFAs are equivalent can be done in P (by observing that DFAs are closed under complementation and intersection, and that $A\subseteq B$ is equivalent to $A\cap \overline{B}=\emptyset$).

As for checking equivalence of NFAs, we know that the equivalence problem is PSPACE-complete (by a simple reduction from universality of NFAs). This means that if the problem was in P, we would get P=PSPACE, which would be a huge and unlikely surprise.

Same goes for checking equivalence of regular expressions - the problem is PSPACE-complete. This post has more details on this