4 ms·

The excerpt on the Boolean Satisfiability Problem reads > The basic concept that people have figured out, so far, is that a number of NP-complete problems can

by drak3 10y ago

The excerpt on the Boolean Satisfiability Problem reads > The basic concept that people have figured out, so far, is that a number of NP-complete problems can likely be solved if we crack the Boolean Satisfiability problem. And > If NP-Complete problems get resolved, it is likely (though nobody knows for sure) that we'll crack every NP-Problem Isn't the definition of a NP-Complete problem exactly that it is in NP _and_ every other problem in NP can be reduced to it in polynomial time. So we know _for sure_ ([Cook71]), that as soon we have a polynomial algorithm for SAT _every_ problem in NP can be solved in polynomial time, and not just some of them as the excerpt claims. Am I missing something? Because this seems like a very confusing, if not downright wrong, way to explain NP-completeness and its link to SAT. [Cook71] Cook, S.A. (1971). "The complexity of theorem proving procedures". Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York. pp. 151–158.

chrisseaton 10y ago
In my opinion there are also serious errors with the description of currying. https://github.com/imposters-handbook/feedback/issues/50 https://github.com/imposters-handbook/feedback/issues/50
- lorenzhs 10y ago
  The lambda calculus excerpt on the site has some issues as well. It says: > Lambda Calculus is reduced from left to right, which is very important No, you can do feasible reductions in any order. The problem is that you need to define β-conversion and normal forms (β normal from is obtained by repeatedly applying β-conversion to the leftmost redex). Also, the example reduction is just wrong. You cannot transform (λx. x x) (λx. x x) into x x (λx. x x) - that's just not how β-reduction works. Applying a β-reduction to that term yields the same term, because you substitute the second expression for x in the first, thus obtaining the input all over.
marcosdumay 10y ago
You aren't missing anything. It's wrong.
lorenzhs 10y ago
Yes, you're absolutely right. The other excerpt paragraph right next to it is correct but terribly misleading: > That "undecidable" part is what makes this problem [the Halting Problem] NP-hard. I mean, that's true - but it's very misleading. The most common context in which NP-hardness is discussed is when talking about NP-complete problems - those that are NP-hard and in NP. The way you go about showing that a problem X is NP-complete is showing that it's in NP (most of the time, this is the easy bit) and then showing that it's at least as hard as some NP-complete problem Y. This is usually done by transforming an arbitrary instance of Y into an instance of X in (deterministic) polynomial time, and showing that the X-instance is satisfiable iff (<=>) the Y-instance is. Then there are problems for which NP-hardness has been shown but it's unclear whether they're in NP. Those are often of a continuous nature. I think deciding whether a level of Super Mario World is doable falls into this category.
acs5 10y ago
Also, the description of the boolean satisfiability problem isn't the boolean satisfiability problem at all, but just what we might call the boolean evaluation problem, or a version of the circuit value problem, which is certainly in P. I have no idea what's going on in the lambda calculus excerpt further down the page, in particular substituting (λx.x x) with (x x)? There seems to be a fairly big misunderstanding here. And lambda calculus isn't reduced in any particular order -- there are many ways to reduce the same term.
- tom_mellior 10y ago
  I was going to post the same thing about satisfiability. The excerpt about the Y combinator is also misleading. There is no practical way in which the Y combinator "finds the fixed point of any function"; (Y cos) certainly does not magically evaluate to 0.793085. I think books like this are a good idea, and having self-taught people write them is also a good idea. BUT it looks like this particular book is in serious need of quality control. (Also it should be split up into several parts. Any book that teaches both the Y combinator and how to configure zsh is... weird.)

by drak3 10y ago

chrisseaton 10y ago

In my opinion there are also serious errors with the description of currying. https://github.com/imposters-handbook/feedback/issues/50 https://github.com/imposters-handbook/feedback/issues/50

lorenzhs 10y ago
The lambda calculus excerpt on the site has some issues as well. It says: > Lambda Calculus is reduced from left to right, which is very important No, you can do feasible reductions in any order. The problem is that you need to define β-conversion and normal forms (β normal from is obtained by repeatedly applying β-conversion to the leftmost redex). Also, the example reduction is just wrong. You cannot transform (λx. x x) (λx. x x) into x x (λx. x x) - that's just not how β-reduction works. Applying a β-reduction to that term yields the same term, because you substitute the second expression for x in the first, thus obtaining the input all over.

marcosdumay 10y ago

You aren't missing anything. It's wrong.

lorenzhs 10y ago

Yes, you're absolutely right. The other excerpt paragraph right next to it is correct but terribly misleading: > That "undecidable" part is what makes this problem [the Halting Problem] NP-hard. I mean, that's true - but it's very misleading. The most common context in which NP-hardness is discussed is when talking about NP-complete problems - those that are NP-hard and in NP. The way you go about showing that a problem X is NP-complete is showing that it's in NP (most of the time, this is the easy bit) and then showing that it's at least as hard as some NP-complete problem Y. This is usually done by transforming an arbitrary instance of Y into an instance of X in (deterministic) polynomial time, and showing that the X-instance is satisfiable iff (<=>) the Y-instance is. Then there are problems for which NP-hardness has been shown but it's unclear whether they're in NP. Those are often of a continuous nature. I think deciding whether a level of Super Mario World is doable falls into this category.

acs5 10y ago

Also, the description of the boolean satisfiability problem isn't the boolean satisfiability problem at all, but just what we might call the boolean evaluation problem, or a version of the circuit value problem, which is certainly in P. I have no idea what's going on in the lambda calculus excerpt further down the page, in particular substituting (λx.x x) with (x x)? There seems to be a fairly big misunderstanding here. And lambda calculus isn't reduced in any particular order -- there are many ways to reduce the same term.

tom_mellior 10y ago
I was going to post the same thing about satisfiability. The excerpt about the Y combinator is also misleading. There is no practical way in which the Y combinator "finds the fixed point of any function"; (Y cos) certainly does not magically evaluate to 0.793085. I think books like this are a good idea, and having self-taught people write them is also a good idea. BUT it looks like this particular book is in serious need of quality control. (Also it should be split up into several parts. Any book that teaches both the Y combinator and how to configure zsh is... weird.)