3 ms·
I had no idea what an e-graph was until 5 minutes ago, but this has the feeling to me of something that is nominally NP complete. Languages tend to be designed
by yarg 3y ago
I had no idea what an e-graph was until 5 minutes ago, but this has the feeling to me of something that is nominally NP complete.
Languages tend to be designed with comprehensibility in mind - so the thoroughly unjustifiable hunch that I'm having is that the vast majority of the extreme complexity possibilities are for languages that no sane human would design, let alone actually work with.
- deredede 3y agoI 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.
- NooneAtAll3 3y agoI still don't have any idea what's an e-graph