News for hackers. Stuff that matters.
Re:NP-complete problem solved with biological motors by hiddencost on Sunday February 28, 2016 @02:07AM (#11190164)
I'm going to provide an avenue for thinking about why the stick sorting example is problematic.

Before starting, you have to specify the the size of the plate / the sorting machine. Let's say it supports 10,000 sticks.

I'm going to give you 20,000 sticks.

Does your machine still solve the problem in O(N)? Nope, it's back to O(n log(n)).

The issue with complexity theory is that it's for _arbitrarily large N_, and solutions that work intuitively for small N often run into walls, especially physical solutions.

EDIT:

BTW, I had to stop and think for a bit on that one. This question made me smile; it reminded me of why I enjoyed school. Great question, where the answer isn't obvious and elucidates something about the nature of complexity and how it disagrees with intuition.

Re:NP-complete problem solved with biological motors by solipsism on Sunday February 28, 2016 @02:55AM (#11190261)
I don't think this is the reason the sorting machine can beat O(nlogn). Just as any real sorting machine is limited in size, every real computer is limited as well. Just as the machine can't hold arbitrarily many (or arbitrarily large) sticks, your computer doesn't have enough memory to hold arbitrarily many (or arbitrarily large) numbers. Complexity theory is predicated on idealized computers (Turing machines with infinitely long tapes, or register machines able to hold infinitely large numbers).
Re:NP-complete problem solved with biological motors by Filligree on Sunday February 28, 2016 @08:26AM (#11190859)
But isn't this just radix sort, effectively? That's linear-time, no problem. There's no fundamental rule saying that sorting has to be O(n lg n), it's only sorting-by-comparison that needs O(N lg n) comparisons.

Though I guess one might point out that, without direct (and infinitely precise!) comparisons, eventually you'll have enough sticks that you won't really be able to tell which is the largest.

Re:NP-complete problem solved with biological motors by gohrt on Sunday February 28, 2016 @02:33AM (#11190221)
You can build an arbitarily large sticky plate in linear time, before using the plate. It doesn't add a log(n) factor.
Re:NP-complete problem solved with biological motors by parenthephobia on Sunday February 28, 2016 @02:58AM (#11190267)
Well, I don't think that's true.

Eventually, the plate will be higher density than the material available at the point of its construction, so it will need to take material from outside the plate's current area to fill it.

As the plate extends further into lower-density regions, it will have to extend its materials gathering exercises further and further away from the actual construction site, so they'll take longer and longer to get there.

Even if the plate is very low density indeed, eventually you'll run out of planet and have to start dismantling the moon - which is quite a long way away - unless the plate has a lower density than the volume of space the moon encloses.