Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The new Gödel Prize winner tastes great and is less filling

blog.computationalcomplexity.org

Post reply on HN
Print view View original

41–50 of 54 posts

Re: The new Gödel Prize winner tastes great and is less filling

#41

Post by zmgsabst »

Dylan16807 wrote: post #40
zmgsabst wrote: post #35

Earlier quoted context omitted.

The difference is deterministic termination: There is no N such that your algorithm is guaranteed to terminate before N flips — even for a single bit. The complexity class in the worst case (100% T) is infinite; it’s only the average cases that have something reasonable. To borrow your phrasing: If you only have a stochastic algorithm, I think you should have to say so.

> the worst case (100% T) You're no longer randomly flipping a coin to get heads or tails at that point. There's a good argument that this is not within the original scenario.

Yes you are — you just have exceptionally bad luck to generate that sequence.

Re: The new Gödel Prize winner tastes great and is less filling

#42

Post by zmgsabst »

geysersam wrote: post #38
zmgsabst wrote: post #35

Earlier quoted context omitted.

The difference is deterministic termination: There is no N such that your algorithm is guaranteed to terminate before N flips — even for a single bit. The complexity class in the worst case (100% T) is infinite; it’s only the average cases that have something reasonable. To borrow your phrasing: If you only have a stochastic algorithm, I think you should have to say so.

You can relax the constraints to bound the cost. If I asked a someone gambling, does it matter if this coin is biased 0.0001%, they will probably say no. And just like that, the algorithm is now guaranteed to terminate. It's a bit unfair to talk about the case (100% T) because in that case you don't have a source of randomness anymore, we've dropped the assumption that you have a source of randomness, and as expected…

You have a source of randomness — you just got exceptionally unlucky. A truly random source can produce the same value indefinitely.

My point is that you have stochastic termination, but not guaranteed termination. Those are different things.

Re: The new Gödel Prize winner tastes great and is less filling

#43

Post by [deleted] »

antics wrote: post #39
zmgsabst wrote: post #35

Earlier quoted context omitted.

The difference is deterministic termination: There is no N such that your algorithm is guaranteed to terminate before N flips — even for a single bit. The complexity class in the worst case (100% T) is infinite; it’s only the average cases that have something reasonable. To borrow your phrasing: If you only have a stochastic algorithm, I think you should have to say so.

Kind of, kind of not. I think it's fair to argue a lot of theory people would argue that it is effectively guaranteed to terminate, for any reasonable definition of "guaranteed." As I mention elsewhere, for a coin where P(H)=0.75, with 600 flips, the probability of not having received an answer is less than 1 divided by the number of atoms in the universe. While this is not 0, neither is the probability of the atoms…

[deleted]

Re: The new Gödel Prize winner tastes great and is less filling

#44

Post by Dylan16807 »

zmgsabst wrote: post #41
Dylan16807 wrote: post #40

Earlier quoted context omitted.

> the worst case (100% T) You're no longer randomly flipping a coin to get heads or tails at that point. There's a good argument that this is not within the original scenario.

Yes you are — you just have exceptionally bad luck to generate that sequence.

Oh, I thought you were saying the coin bias was 100%. I misread how you were using complexity class.

Still, when a worst case is physically impossible I don't think it needs a mandatory disclaimer.

Re: The new Gödel Prize winner tastes great and is less filling

#45

Post by Dylan16807 »

zmgsabst wrote: post #42
geysersam wrote: post #38

Earlier quoted context omitted.

You can relax the constraints to bound the cost. If I asked a someone gambling, does it matter if this coin is biased 0.0001%, they will probably say no. And just like that, the algorithm is now guaranteed to terminate. It's a bit unfair to talk about the case (100% T) because in that case you don't have a source of randomness anymore, we've dropped the assumption that you have a source of randomness, and as expected…

You have a source of randomness — you just got exceptionally unlucky. A truly random source can produce the same value indefinitely. My point is that you have stochastic termination, but not guaranteed termination. Those are different things.

> My point is that you have stochastic termination, but not guaranteed termination. Those are different things.

You missed their suggestion about that.

If you rephrase the algorithm as one that almost almost almost almost almost completely eliminates bias, you can guarantee termination by giving up after a certain number of repetitions.

Re: The new Gödel Prize winner tastes great and is less filling

#46

Post by zmgsabst »

Dylan16807 wrote: post #44
zmgsabst wrote: post #41

Earlier quoted context omitted.

Yes you are — you just have exceptionally bad luck to generate that sequence.

Oh, I thought you were saying the coin bias was 100%. I misread how you were using complexity class. Still, when a worst case is physically impossible I don't think it needs a mandatory disclaimer.

All infinite sequences are physically impossible, but they’re the basis of asymptotics; arbitrary failure and non-production of entropy are still physically possible.

Re: The new Gödel Prize winner tastes great and is less filling

#47

Post by zmgsabst »

Dylan16807 wrote: post #45
zmgsabst wrote: post #42

Earlier quoted context omitted.

You have a source of randomness — you just got exceptionally unlucky. A truly random source can produce the same value indefinitely. My point is that you have stochastic termination, but not guaranteed termination. Those are different things.

> My point is that you have stochastic termination, but not guaranteed termination. Those are different things. You missed their suggestion about that. If you rephrase the algorithm as one that almost almost almost almost almost completely eliminates bias, you can guarantee termination by giving up after a certain number of repetitions.

Sure — but now we’re back in the case the person above me was calling out and I was emphasizing by pointing out the stochastic nature: you moved the goal posts.

From their comment:

> Which is why it's not really incredible that it can be done: it can't, not as the problem was originally stated. What can be done is solving a different (but useful) problem than the one originally posed.

You can have an arbitrarily small bias, at the cost of increased runtime — but you can’t have a zero bias algorithm that always terminates. You have to move the goalposts (allowing some bias or exceedingly rare cases to not terminate).

I’m not sure why people have such a hard time admitting that.

Re: The new Gödel Prize winner tastes great and is less filling

#48

Post by Dylan16807 »

zmgsabst wrote: post #47
Dylan16807 wrote: post #45

Earlier quoted context omitted.

> My point is that you have stochastic termination, but not guaranteed termination. Those are different things. You missed their suggestion about that. If you rephrase the algorithm as one that almost almost almost almost almost completely eliminates bias, you can guarantee termination by giving up after a certain number of repetitions.

Sure — but now we’re back in the case the person above me was calling out and I was emphasizing by pointing out the stochastic nature: you moved the goal posts. From their comment: > Which is why it's not really incredible that it can be done: it can't, not as the problem was originally stated. What can be done is solving a different (but useful) problem than the one originally posed. You can have an arbitrarily smal…

I don't think the termination thing is moving the goalposts.

If you have infinite time, then you can wait for it to take more than a few hundred iterations.

If you don't have infinite time, it won't take more than a few hundred iterations.

Also "constant time" wasn't even part of the original promise! If a goalpost was moved, it was by the person that decided on that requirement after the fact.

Re: The new Gödel Prize winner tastes great and is less filling

#49

Post by dataflow »

Dylan16807 wrote: post #48
zmgsabst wrote: post #47

Earlier quoted context omitted.

Sure — but now we’re back in the case the person above me was calling out and I was emphasizing by pointing out the stochastic nature: you moved the goal posts. From their comment: > Which is why it's not really incredible that it can be done: it can't, not as the problem was originally stated. What can be done is solving a different (but useful) problem than the one originally posed. You can have an arbitrarily smal…

I don't think the termination thing is moving the goalposts. If you have infinite time, then you can wait for it to take more than a few hundred iterations. If you don't have infinite time, it won't take more than a few hundred iterations. Also "constant time" wasn't even part of the original promise! If a goalpost was moved, it was by the person that decided on that requirement after the fact.

> If you have infinite time, then you can wait for it to take more than a few hundred iterations.

To be clear, you're making this argument while also arguing "this wouldn't happen in the real world". [1] You can't have it both ways.

> Also "constant time" wasn't even part of the original promise!

We're not even asking for "constant time". We're literally only asking for "will finish in any bounded amount of time". Even an exponential time bound would've been better than unbounded!

A simulator that can't even promise to get to step #2 of the simulation in any bounded amount of time very much needs a giant proactive asterisk on its labeling, because that's not what people understand to be a simulator. Again, if you sold someone that in such a manner that obscured this fact, they would absolutely be justified in wanting their money back.

[1] https://news.ycombinator.com/item?id=44228568

Re: The new Gödel Prize winner tastes great and is less filling

#50

Post by Dylan16807 »

dataflow wrote: post #49
Dylan16807 wrote: post #48

Earlier quoted context omitted.

I don't think the termination thing is moving the goalposts. If you have infinite time, then you can wait for it to take more than a few hundred iterations. If you don't have infinite time, it won't take more than a few hundred iterations. Also "constant time" wasn't even part of the original promise! If a goalpost was moved, it was by the person that decided on that requirement after the fact.

> If you have infinite time, then you can wait for it to take more than a few hundred iterations. To be clear, you're making this argument while also arguing "this wouldn't happen in the real world". [1] You can't have it both ways. > Also "constant time" wasn't even part of the original promise! We're not even asking for "constant time". We're literally only asking for "will finish in any bounded amount of time". Ev…

> You can't have it both ways.

I addressed that in my next sentence! The whole point of making it two sentences was to split up the real world and not real world cases. Come on.

> We're not even asking for "constant time". We're literally only asking for "will finish in any bounded amount of time". Even an exponential time bound would've been better than this!

N is 1. Every bound is a constant bound.

> if you sold someone that in such a manner that obscured this fact, they would absolutely be justified in wanting their money back.

They would not be entitled to a penny back because it's impossible for them to hit the failure case.

Even if they could hit it, nobody is getting a refund for "it crashes once per googolplex runs".

Post reply on HN