4 ms·

what happens in the example i gave above? if the minimum complexity of solving any np-complete problem is O(n^2e80) then we'd need such massively parallel compu

what happens in the example i gave above? if the minimum complexity of solving any np-complete problem is O(n^2e80) then we'd need such massively parallel computing that you'd have to turn pretty much every atom in the universe into a computing device. i agree that p != np is the instinctive model most theoreticians have about the universe, but if science has taught us anything in the last 100 years, it's that our instincts are often wrong, and the story of science will probably never be finished.

Udo 15y ago
Absolutely, but I'd say that the idea of brute-forcing the entire universe - while theoretically and mathematically sound - goes against the spirit of what we're trying to express with Big O. Solutions like these work in a theoretical universe with infinite matter and possibly over infinite time, but if the world is indeed finite (which it may very well be) any Big O expression containing the sum of all states of all atoms in the universe does contain a practical infinity.
- MarkPNeyer 15y ago
  i'm not sure what you mean by the 'spirit' of Big-O; i find the question fascinating because it is relatively easy to understand the concepts involved, yet it's been 40+ years since we understood enough to be able to ask the question, and we still don't know the answer. when you couple that with the fact that the prevailing wisdom that our inability to find an algorithm implies that it can't exist, the contrarian in me goes nuts: the academic attitude is always "we're so smart, if we can't find it, it must not exist," and i get a kick out of arguing for more humility on their part. even though a polynomial-time algorithm with a massive polynomial would still be computationally intractable, even a proof that such an algorithm exists, but is too complicated to express using all the atoms in the universe as bits would probably open the doors to all kinds of proofs and techniques we cant' even imagine.

Udo 15y ago

Absolutely, but I'd say that the idea of brute-forcing the entire universe - while theoretically and mathematically sound - goes against the spirit of what we're trying to express with Big O. Solutions like these work in a theoretical universe with infinite matter and possibly over infinite time, but if the world is indeed finite (which it may very well be) any Big O expression containing the sum of all states of all atoms in the universe does contain a practical infinity.

MarkPNeyer 15y ago
i'm not sure what you mean by the 'spirit' of Big-O; i find the question fascinating because it is relatively easy to understand the concepts involved, yet it's been 40+ years since we understood enough to be able to ask the question, and we still don't know the answer. when you couple that with the fact that the prevailing wisdom that our inability to find an algorithm implies that it can't exist, the contrarian in me goes nuts: the academic attitude is always "we're so smart, if we can't find it, it must not exist," and i get a kick out of arguing for more humility on their part. even though a polynomial-time algorithm with a massive polynomial would still be computationally intractable, even a proof that such an algorithm exists, but is too complicated to express using all the atoms in the universe as bits would probably open the doors to all kinds of proofs and techniques we cant' even imagine.