2 ms·
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 a
by advisedwang 4mo 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]:
for each element:
cut a spaghetti strand to the a the length of the elemnet
add strand to bundle of spaghetti
hold spaghetti bundle vertical
lower spaghetti bundle to a flat surface.
loosen grip so that each spaghetti strand comes to rest on flat surface
while there is spaghetti in the bundle:
lower a second flat surface above the bundle until it touches the topmost spaghetti piece
remove the piece, and output it's length
[1] which I learned about in "The New Turing Ominbus" by A K Dewdney
- DroneBetter 4mo agoi 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.
- kadoban 4mo agoWhat 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.
- IAmBroom 4mo agoFor purely randomly distributed groups of n things.
- recursivecaveat 4mo agoI 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.