4 ms·
I agree that this result is wholly unsurprising (I had just assumed it to be true, but it is nice to have confirmation). I am not sure I understand your commen
by deredede 3y ago
I agree that this result is wholly unsurprising (I had just assumed it to be true, but it is nice to have confirmation).
I am not sure I understand your comment on language structure. E-graphs are used to reason automatically about equivalence of (PL or) math expressions, there is quite a lot of possible combinations of assembly opcodes or other bytecodes and do not humans interact with them directly but compilers and formal tools have to.
(Edit: typo, meant humans do not interact with bytecode directly... Usually)
- yarg 3y agoIt'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.