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...
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.
