News for hackers. Stuff that matters.
Re:NP-complete problem solved with biological motors by claudius on Sunday February 28, 2016 @12:34PM (#11191503)
> However, how does sorting, say, the physical length of sticks come into this? If you stand them all in a bundle you can easily select out the tallest, and then the next tallest, etc, by e.g., lowering a sticky horizontal plate.

But here you are only linear in the number of plate-lowering- and longest-stick-removal-operations. The actual number of comparisons you do in this example is still very much quadratic, as, in every step, you have to check every stick on whether or not it touches the plate; you just found a very fast way to check this (but still linear in the number of sticks remaining).

There are no comments on this comment yet.