News for hackers. Stuff that matters.

A comment on Complexity Theory’s 50-Year Journey to the Limits of Knowledge. Parent comment

Re:Complexity Theory’s 50-Year Journey to the Limits of Know... by quickthrower2 on Saturday August 19, 2023 @05:23AM (#37186994)
A cheeky way to do it is this, reuse the randomness that we are assuming about the input data:

1. Data structure in pseudo code:

    max = 0
    items = []
    def add(x: int32):
       max = max(x, max)
       items.push(x)
2. Algorithm:

    def doit()
        if max == int32.max return 0
        sleep (1000)
        return 0
As you add items to this data structure, on average over all possible data inputs the time taken for doit() will tend from K+1000ms to a constant K.
[ Parent | on HN ]
Re:Complexity Theory’s 50-Year Journey to the Limits of Know... by daveFNbuck on Sunday August 20, 2023 @02:56AM (#37196849)
That's what I'm saying. The runtime will go down to a constant. It can't keep decreasing forever.
[ Parent | on HN ]
Re:Complexity Theory’s 50-Year Journey to the Limits of Know... by quickthrower2 on Sunday August 20, 2023 @03:41AM (#37197015)
“Tend to” is a mathematical term mean get closer to. Formally, for any e as small as you like there exists an N within e of the value being approached.

This is possible because we are sampling a probability distribution. A dice is discrete but the probability of rolling a 1 as the number of sides increases tends to zero even if there is a whole “1” in a given dice.

[ Parent | on HN ]
Re:Complexity Theory’s 50-Year Journey to the Limits of Know... by daveFNbuck on Sunday August 20, 2023 @10:02PM (#37204716)
An algorithm can't have that property for its expected runtime, as it can only look at a sub-constant amount of the input of it runs in sub-constant time.

it's not possible for it to behave differently as n increases because it doesn't have enough time to distinguish between different values of n once it's large enough.

[ Parent | on HN ]