Time complexity to minimize Finite Automata

Question

According to  this Hopcroft's algorithm , we can efficiently minimize a Finite automata in $O(nlogn)$  time (polynomial time algo) then why it is said that Minimizing Finite Automata is computationally hard according to this link ?

Comments

No, in worst case it is O(ns log n), where n is the number of states and s is the size of the alphabet. See this:
https://en.wikipedia.org/wiki/DFA_minimization#Hopcroft's_algorithm

---

@Abhishek , I think ,This exponential time is for changing non-deterministic machine model to deterministic machine model..If our NFA has n states then number of states in its equivalent minimal DFA should be atmost 2ⁿ states..so , this conversion procedure from non-deterministic machine to deterministic machine takes exponential time...But in case of minimization of DFA , we make equivalence classes which represent different states in the minimal DFA...This procedure can take O(n²) or O(nlogn) time...Shai sir has explained O(n²)   time algorithm to minimize finite automata in his video but not O(nlogn)..

---

0k ankit

Answer 1

Hopcroft's algorithm, which You are talking about,  which can efficiently minimize a Finite automata in $O(nlogn)$ time (polynomial time algo), is for "Minimization of a Deterministic FA".

And the other link is about "Minimizing a Non-deterministic FA Which is computationally hard (Even if there is slight Non-determinism).