Regex matching with backreferences is NP-hard.
> SAT is an NP-complete problem, meaning that it is at least as hard as any other problem in NP
I think this statement is backwards. Instead, any other problem in NP is at least as hard as SAT
Funnily, although we usually think of it as having complexity O(log n), that does not hold true for the Turing machine model, with which the complexity classes P and NP are defined.
` binary search is in NP (because it is in P),`
P = NP!? Casually proved in a HN comment?
NP-complete is the intersection of sets NP and NP-hard , but not the part of NP that contains P.
Lots of NP-hard problems are not in NP is important.
https://en.wikipedia.org/wiki/NP-hardness#/media/File:P_np_n...
More accurate than “an NP-complete subset of SAT” would be to say that SAT is polynomial-time reducible to 3-SAT or that we can solve SAT in terms of 3-SAT.
Combining both of these, each is reducible to the other. In some sense, they are the same problem. 3-SAT imposes just enough structure to force it into NP-complete. 2-SAT is in P.
SAT conferences aren't on youtube either :(
The calculation of the pure function is still used for any other combination of input values.
Supercompilation looks at the unevaluated symbolic recursive code and replaces the code in some cases with simpler, specialized code tuned to the actual input values, so does a memoizing not only of the result, but the code used to calculate the function to begin with.
> deep program transformation
It doesn't have to be deep, does it? You can't transform the entire program, so there's an arbitrary cut-off anyway.
Here is some discussion here on why a pretty serious for GHC stalled: https://www.reddit.com/r/haskell/comments/2s97d0/the_state_a...
In fact, supercompilation subsumes many common optimizations, such as function inlining, constant propagation, list fusion, etc. So we can say that it's actually used "to a small degree", although I wouldn't really call it "supercompilation" per se.
The reason that full-blown supercompilation is not used is that it's too unpredictable -- the direct consequence of being too smart. I've elaborated on it in the final section of the blog post.
