4 ms·

> (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) D

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

munk-a 6y ago
"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.
- cratermoon 6y ago
  That sounds like a quote from a Douglas Adam book.
- kryptiskt 6y ago
  Narbonic got close http://narbonic.com/wordpress/wp-content/uploads/2006/12/061207.jpg http://narbonic.com/wordpress/wp-content/uploads/2006/12/061...
comex 6y ago
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 https://cs.stackexchange.com/questions/2712/does-npnp-np
- jbay808 6y ago
  Very interesting! Thank you for putting on your pedant hat!
- qsort 6y ago
  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.
ncmncm 6y ago
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.

munk-a 6y ago

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

cratermoon 6y ago
That sounds like a quote from a Douglas Adam book.
kryptiskt 6y ago
Narbonic got close http://narbonic.com/wordpress/wp-content/uploads/2006/12/061207.jpg http://narbonic.com/wordpress/wp-content/uploads/2006/12/061...

comex 6y ago

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 https://cs.stackexchange.com/questions/2712/does-npnp-np

jbay808 6y ago
Very interesting! Thank you for putting on your pedant hat!
qsort 6y ago
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.

ncmncm 6y ago

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.