Hacker News Reader

Comment by munk-a | Hacker News Reader

I absolutely loved learning about Bead Sort when I was in Uni. I was taking a class on algorithm design and Big-O notation and ended up reading through the sorting algorithms page on wikipedia[1] and then wandering off the garden path investigating a few.

There are several amusing ways that standard algorithmic analysis has been subverted with creative solutions (i.e. if you subscribe to the many-worlds theory then bogosort is always O(1) for at least one universe - you just need to discard the incorrect universes) but beadsort stood out as a really fun way to turn the problem on its head - the fact that it appears to be inspired from misusing an abacus just makes it even better.

It's a great example of why having people who can think outside of the box can be a good asset - approaching problems from unexpected directions can yield valuable and novel solutions.

1. https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_o...

View on HN

> (i.e. if you subscribe to the many-worlds theory then bogosort is always O(1) for at least one universe - you just need to discard the incorrect universes)

Does this same line of thinking conclude that P=NP in at least one universe, too? You can use a radioactive decay counter to generate quantum random numbers, interpret them as a answer to an NP problem, and then verify the solution in polynomial time the normal way? In at least one universe, that will always work on the first try.

"It's amazing what you can do if you're willing to sacrifice a few universes to get out of doing some addition" - probably no one ever, but it should've been said before now.

That sounds like a quote from a Douglas Adam book.

Narbonic got close http://narbonic.com/wordpress/wp-content/uploads/2006/12/061...

puts on pedant’s hat

That wouldn’t actually make P = NP, because P is defined mathematically from first principles rather than being based on the rules of the universe. However, it would shift the class of practically computable problems from being ‘like P’ (but with limits on the runtime and memory usage achievable), to being ‘like P^NP’, P with an NP oracle, which is surprisingly a different complexity class from NP. At least, that’s what I gather based on Wikipedia and Stack Overflow [1]; I’m not an expert on the subject so I could be mistaken.

[1] https://cs.stackexchange.com/questions/2712/does-npnp-np

Very interesting! Thank you for putting on your pedant hat!

puts on hat from the second level of the pedant hierarchy

Assuming P!=NP!=co-NP, that computational model is equivalent to either NP or co-NP depending on the multiverse semantics you are using, not P^NP. If you can send the computation through multiple universes and get back a 'YES' or 'NO' answer, depending on whether the 'YES' or 'NO' is quantified existentially or universally on the leaves of the computation tree, you get NP or co-NP. Intuitively speaking, imagine you have a 3-SAT instance; you can send one assignment of truth values to the variables to each parallel universe for computation. If the multiverse answers you 'YES' if there exists one universe that says 'YES', that solves NP problems in P-time. If the multiverse answers you 'YES' if all universes say 'YES', that solves co-NP problems in P time.

That's not how bogosort works. You just make a separate universe for each of N! possible orders, and then discard all the universes where it is not already sorted.

A universe where P=NP might not support life. Or, might not support yours. Or, only yours.

I'm taking a graduate algorithms class right now, and stumbled upon the bead sort wiki page.

These methods are quite interesting! The bound of O(n log n) only applies when using the traditional greater/less than comparison model

> only applies when using the traditional greater/less than comparison model

What do you mean by this?

The bound is a bound on comparaison sort not a general bound on sorting.

If you don't use comparaison you can sort faster. Pigeonhole sort is linear for example.

Right, comparative and non-comparative sorting algorithms.

I'd say radix sort is the canonical example of a non-comparative sorting algorithm.

Reply on news.ycombinator.com