News for hackers. Stuff that matters.
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).

There are no comments on this comment yet.