| ▲ | advisedwang 4 days ago | |||||||
It doesn't disprove a theory if it results in the physical universe violating NP!=P. In fact, we already know the universe violates NP!=P via the O(N) sorting algorithm[1]:
[1] which I learned about in "The New Turing Ominbus" by A K Dewdney | ||||||||
| ▲ | kadoban 3 days ago | parent | next [-] | |||||||
What does sorting have to do with violating p != np? The common bound on sorting is you can't do better than O(n lg n) worst-case, but that is strictly only for comparison sorts anyway. | ||||||||
| ||||||||
| ▲ | recursivecaveat 3 days ago | parent | prev | next [-] | |||||||
I feel like there's some hidden complexity there. For any finite flat surface there's a point where not all the spaghetti will fit on it simultaneously. So you have to do O(N) compression steps to find the bundle with the long strand. Locating the strand within the bundle also seems non-trivial if it's big enough. Both are easier to see if you start thinking about scaling to sorting like, square miles of spaghetti at a time. | ||||||||
| ▲ | DroneBetter 4 days ago | parent | prev [-] | |||||||
i hate every time i hear about spaghettisort. it is still O(n) weight to transport, so O(n^2) amortised; if you liken having a stronger hand that can carry more spaghetti to parallelisation, it's beaten by O(log^2 n) sorting algorithms on parallelised classical computers. | ||||||||