3 ms·
It's like your willfully misconstruing to make what points here? >It doesn't follow that all instances of e-graphs are unsolvable in polynomial time, only that
by mathisfun123 3y ago
It's like your willfully misconstruing to make what points here?
>It doesn't follow that all instances of e-graphs are unsolvable in polynomial time, only that some aren't.
Yes and hardness results are about proving lower bounds on worst case complexity not best case or sometimes case or whatever-you-chose-as-meaningful case.
- JonChesterfield 3y agoLet's not rule out that I may just be wrong. However e-graphs are not really a general purpose thing, they're a bespoke creation for partially solving phase ordering in compilers, intermixed with the DAG tiling problem from instruction selection. Specifically, e-graphs are used with respect to an ISA from which the cost model is derived. My intuition is that this constrains the structure sufficiently that polynomial solutions can be found. Probably involving a partial order calculated ahead of time. For me, whether the result in the opening post is applicable to uses of e-graphs in compilers has a strong influence over whether I need to worry about it or not. I'm on the fence about e-graphs as a model. If rolling one into production means I'll occasionally hit exponential increases in running time as heuristics fall over, that's an argument against. If those cliffs are unreachable for a given ISA, they don't matter.
- mathisfun123 3y ago>if those cliffs are unreachable for a given ISA, they don't matter By rice's theorem, for any ISA that has a jmp or mov, there is no way to know/prove/predict this. So you're still not saying anything useful.