[jbay808]

> (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.

[comex]

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

[qsort]

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.

[jbay808]

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

[munk-a]

"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.

[kryptiskt]

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

[cratermoon]

That sounds like a quote from a Douglas Adam book.

[ncmncm]

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.