Ultimately, the problem comes down to assigning exactly half of the numbers from 1 through N a sign of +1, and the other half -1, so that the sum of the numbers is 0. For N = 4 there is one solution
1 2 3 4
+1 -1 -1 +1
and its "reflection" that is obtained by multiplying everything by -1.
It's easy to prove that a solution exists if and only if N is a multiple of 4. For N = 8, Barrow proposes some new solutions.
There is a connection here to the Thue-Morse sequence t(i), which assigns to i either +1 or -1, according to the parity of the number of 1's in the binary expansion of i. An old theorem of D. H. Lehmer implies that
Σ0 ≤ i < 2k t(i) p(i) = 0
for any polynomial of degree < k. So in particular, the Thue-Morse sequence gives an infinite family of solutions to the wiggle-free rowing problem, whenever N is a power of 2. In particular, for N = 8, Barrow's solution (d) is given by the Thue-Morse sequence.
As an aside, Barrow implies something about the complexity of the problem in his abstract. He says, "We show that the problem of finding the zero-moment rigs is equivalent to a version of the NP-complete Subset Sum problem." No, not really. He showed that his problem is a special case of the subset-sum problem, which says nothing at all about its complexity. After all, his problem is also a special case of the halting problem! And in any event, since it is easy to show that solutions exist if and only if N is a multiple of 4, the decision problem's complexity is trivial.
This is yet another example of the rule that says "Whenever scientists or mathematicians with no formal training in computer science talk about complexity theory, with high probability they are quickly going to say something stupid." For another example, see here. Of course, if I were to write about physics, no doubt I would say something equally stupid.
5 comments:
This is exactly why if one is submitting an "out of specialty" article, one should ALWAYS run it by a specialist. :-)
This seems more like bad wording than anything else. If they had written something like "problem of finding the zero-moment rigs is equivalent to a version of the Subset Sum problem (which is NP-complete)." then the intended meaning would be obvious. This seems more like bad wording than actually being outright wrong.
Joshua - I agree that the wording is bad, but I don't agree that your rewording is any improvement. The problem isn't equivalent to a version of the Subset Sum problem, in the sense that most computer scientists would understand "equivalent" and "version".
Yeah. Special case makes a lot more sense. Honestly it almost reads like a statement one would make to a non-math person. Special case is a term mathematicians in general use but if I were trying to explain something like this to a non-math person I might very well use version. (There's really no good colloquial term for what mean by a special case. Specific instance? Sounds awkward and isn't quite the same thing)
I'm surprised this wasn't picked by the reviewer.
I independently emailed John Barrow at length, to the same end. He's now removed the stuff about NP-completeness, and just observes that it's a very special case of that problem. You and I are both thanked.
Post a Comment