Solving SAT via Positive Supercompilation(hirrolot.github.io) |
Solving SAT via Positive Supercompilation(hirrolot.github.io) |
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.
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.
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.
"P" is the class of problems that can be solved by a deterministic Turing machine in polynomial time. "NP" stands for "nondeterministic polynomial time," and is the class of problems for which a solution can be _verified_ in polynomial time by a deterministic Turing machine, given the correct "hint" or "certificate." Every problem in P is also in NP, since if a problem can be solved in polynomial time, its solution can certainly be verified in polynomial time (just solve the problem again).
Certainly P is a subset of NP, but is this statement always true?
Consider a Galton board where a marble is dropped into an array of pegs. At each peg, it can go left or right at random (assume it never bounces further). After some number of choices, it falls into a slot.
Finding a solution (a slot that a marble can fall into) is easy: drop one marble. But it could take many marbles to verify that a marble can fall into a given slot.
As described, that is easy: all left choices, all right choices, everything in between. But imagine that the choices aren't fair, directly observable, or linear (LR != RL). Then it gets tricky.
I've never thought about non-deterministic problems of that sort in the context of computational theory, but it isn't uncommon in nature.
Indeed the Cook-Levin theorem
> https://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem
which actually proves that there exist NP-complete problems in NP is not a trivial result (and was at that time a highly surprising one).
So, indeed, "one half of the proof" has been done; the other half (which seems to be much harder) of P vs NP is still open.
If for example, you model it as a graph, with a peg represented by a node, and a bounce direction to another peg with a directed edge. Assign probabilities to all the edges. Then you cqn simply flood search outwards to the end of the graph, accumulating probabilities by multiplication. Any node on the boundary with probability higher than zero can be reached, given enough balls. This job is clearly in P.
I'm not sure it makes sense to talk about "P" for physical problems without a computational model, but I'm not a complexity theorist
Decision problems are much easier to reason about, which is why they are used to construct and define the fundamental complexity classes, though it is certainly possible to define analogous classes for different types of problems. See for example, Krentel (1988) "The complexity of optimization problems", which considers TSP-OPT: https://doi.org/10.1016/0022-0000(88)90039-6
