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

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 https://en.wikipedia.org/wiki/EXPSPACE