Does this really violate logic? And which miracle is really more impressive?
It doesn’t seem to me that sorting a list in linear time really violates logic itself. It seems plausible that a divine being might be able to do any number of things that would violate the conditions that prevent sorting in linear time. e.g. perform multiple operations or comparisons at once. Or omnisciently perceiving the distribution of the numbers and then using it to perform a bucket sort.
I’m not saying that sorting in linear time isn’t impressive. But the crowd does have a point here. Violating conservation of mass does seem more impressive.
For SMBC fans who think the bonus panel and hovertext are essential to the comic, here they are.
“All technical quibbles may be sent to my email, where they will be figuratively burned.”
Mitch4/guero: If you’re going to allow that God knows all things (which is reasonable), why not also allow that he can move more than one element at a time?:
Scott’s point that complexity is in the number of operations, so that parallelizing doesn’t affect the complexity is well taken, but there is some ambiguity in what consistutes an “operation.” If for a divine being, moving multiple elements at the same time is no more “work,” then all the movements done in unison should count as an “operation.”
For example, Grover’s algorithm, on average, finds an element in an unsorted database of size N in O(sqrt(N)) operations. That’s clearly impossible classically, but it’s possible because Grover’s algorithm is a quantum algorithm, and so its operations can perform steps on every element of the database simultaneously.
And y’know what? … That does not violate logic itself! 🙂