• barsoap@lemm.ee
    link
    fedilink
    English
    arrow-up
    1
    arrow-down
    1
    ·
    2 months ago

    The other way around: As long as you accept that cause and effect are a thing, you must accept that there are things that are, fundamentally, uncomputable. And as our universe very much does seem to have cause and effect that’s a physical law, likewise is complexity theory. Differently put: God can’t sort a list with fewer than O(n log n) comparisons.