We know that some algorithms are fundamentally harder than others. Deciding whether two regexps are equivalent requires EXPSPACE which is known to be a strict superset of NP[1]. We just haven't proved whether P != NP.

[1] https://en.wikipedia.org/wiki/EXPSPACE