[HN Gopher] The E-graph extraction problem is NP-complete
___________________________________________________________________
The E-graph extraction problem is NP-complete
Author : matt_d
Score : 36 points
Date : 2023-06-23 23:22 UTC (23 hours ago)
(HTM) web link (effect.systems)
(TXT) w3m dump (effect.systems)
| JonChesterfield wrote:
| Biggest tile first, nearest entry node first should be linear
| time.
|
| Decent chance you can hack 'optimal' out in a reasonable
| timeframe if you run that heuristic first and then prune the
| search space to discard any solution that would be worse than
| said first guess.
|
| I'm certainly not convinced by the argument that optimal egraph
| is equivalent to the minimum set cover problem and thus in NP. I
| can believe that egraph extraction can be modelled as minimum set
| cover, but there's a lot of additional structure in the egraph
| which I suspect takes us out of the general case.
|
| By analogy, it is known that register allocation is NP complete
| because it's graph colouring. Despite that, register allocation
| on a chordal graph can be done in linear time, and SSA form gives
| you a chordal graph. Being a specific instance of a hard problem
| matters.
| mathisfun123 wrote:
| >I'm certainly not convinced by the argument that optimal
| egraph is equivalent to the minimum set cover problem and thus
| in NP. I can believe that egraph extraction can be modelled as
| minimum set cover
|
| Are you like actually misunderstanding or are you trying to say
| something else - egraph is in np because it's equivalent to ilp
| and it's complete because you can reduce set cover to _it_ not
| the other way around (the reduction always goes _to_ the
| problem not _from_ the problem in a completeness proof).
|
| >Despite that, register allocation on a chordal graph can be
| done in linear time, and SSA form gives you a chordal graph.
|
| This isn't saying much since SSA construction (phi elimination)
| isn't linear.
| JonChesterfield wrote:
| I'm least one of misunderstanding and disagreeing.
|
| Start with a set cover problem, NP. OK. Translate it
| mechanically to an e-graph in polynomial time, sure, that
| instance of the e-graph is still unsolvable in polynomial
| time. It doesn't follow that all instances of e-graphs are
| unsolvable in polynomial time, only that some aren't.
|
| Your e-graph is really heavily constrained by the ISA and
| optionally by the ABI. It's also constrained by the code it
| was created from which will tend to have its own constraints.
| Constraints can lead to faster solutions.
|
| SSA construction is putting phi's in, if you're using them
| instead of block arguments. Destruction is taking phis out.
| Whether that's linear time or polynomial or non-polynomial
| depends on how optimal a job of eliding copies you choose to
| do.
| mathisfun123 wrote:
| 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 wrote:
| Let'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.
| nextaccountic wrote:
| Plenty of NP-complete problems have easy instances. Indeed
| for a lot of problems there's an assumption that most
| instances that naturally arise are easier and well solved
| by heuristics but there are _some_ pathological instances
| that aren 't but don't appear in practice
|
| Also: if you are okay with heuristics that aren't
| guaranteed to output the optimal answer the whole point is
| moot
| based2 wrote:
| https://egraphs-good.github.io/
| guimplen wrote:
| The problem is not stated clearly.
| romes wrote:
| Great to see this! Funnily, I was _just now_ working on a problem
| to which I 'm trying to apply e-graphs (using my -- shameless
| plug -- haskell e-graphs/eqsat library[1])
|
| [1] https://github.com/alt-romes/hegg
| nextaccountic wrote:
| Just curious, what's the problem you are solving?
| emmender wrote:
| Proving a problem is np-complete should not be news. what should
| be news is when a problem has a P algo. (example, primes is in P)
|
| my cynical eye sees this as an over-eager grad student rushing
| out his/her discovery onto hacker news. Next thing you know, an
| FPTAS for it may rear its ugly head.
| tekknolagi wrote:
| This is a breathtakingly rude comment. The blog post author is
| not some random grad student looking at another's work; he is
| actively working on egglog & is one of the key people driving
| work in the e-graphs space.
| emmender wrote:
| My apologies, I didnt intend to be rude..
|
| Any discovery is a step forward (whether it is news or not)..
| deredede wrote:
| I disagree. E-graphs as a data structure are used to represent
| an exponential combination of terms in a manageable (ie
| polynomial) structure. Thus, it is interesting to know what the
| limits of that "compression" are - what we can do in the
| polynomial representation and when we have to fall back to an
| exponential (or make compromises).
| yarg wrote:
| 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 wrote:
| 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)
| NooneAtAll3 wrote:
| I still don't have any idea what's an e-graph
| EdSchouten wrote:
| This blog post could really use links to other sources.
|
| First of all, I had no idea what an E-graph was, so I had to
| search for that myself.
|
| Then the post presents the problem itself, without explaining a
| practical situation in which you'd need to compute/solve this.
| Would this be used by a compiler to come up with an optional
| execution strategy? Or an interpreter to evaluate terms?
|
| It talks about the use of a cost function, but to me it's not
| clear where it comes from, and what the cost represents. Would
| that be CPU cycles? Memory use?
|
| I decide to do a Google search for "E-graph extraction problem",
| but apart from the blog post itself, I get no meaningful results.
| I feel lost.
___________________________________________________________________
(page generated 2023-06-24 23:02 UTC)