So how are we supposed to solve ELK, if we are to assume that it’s intractable?
A different answer to this could be that a “solution” to ELK is one that is computable, even if intractable. By analogy, algorithmic “solutions” to probabilistic inference on Bayes nets are still solutions even though the problem is provably NP-hard. It’s up to the authors of ELK to disambiguate what they’re looking for in a “solution,” and I like the ideas here (especially in Level 2), but just wanted to point out this alternative to the premise.
A different answer to this could be that a “solution” to ELK is one that is computable, even if intractable. By analogy, algorithmic “solutions” to probabilistic inference on Bayes nets are still solutions even though the problem is provably NP-hard. It’s up to the authors of ELK to disambiguate what they’re looking for in a “solution,” and I like the ideas here (especially in Level 2), but just wanted to point out this alternative to the premise.