It's turtles all the way down. > do not humans interact with them directly but compilers... So compiler programmers deal with them and humans designed them to

It's turtles all the way down. > do not humans interact with them directly but compilers... So compiler programmers deal with them and humans designed them to be dealt with by the people that write compilers. There's a major selection bias active here - the e-graph is a reflection of the language (and perhaps the target ISA) and its complexities. Since at each level it's likely to have been designed for comprehensibility it seems to me unlikely that any given example will be buried in the intractable heart of NP. But as I said, it's a hunch.