6 ms·
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
by emmender 3y ago
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.
- deredede 3y agoI 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).
- tekknolagi 3y agoThis 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 3y agoMy apologies, I didnt intend to be rude.. Any discovery is a step forward (whether it is news or not)..