The Asynchronous Computability Theorem | Hacker News Reader

The Asynchronous Computability Theorem

medium.com

125 pointsheydenberk9 comments

Beware of taking impossibility proofs too seriously. They should always be interpreted to mean "you cannot achieve this goal in this model," rather than "you cannot achieve this goal."

"As far as the laws of mathematics refer to reality, they are not certain; and as far as they are certain, they do not refer to reality."

  -- Einstein (?)

In particular, impossibility results do not rule out approximate solutions that are good enough for practical purposes.

Unless it is an "impossibility of approximation" theorem.

Even that is frequently misleading. Take the problem of finding a maximum independent set. You can show that if you manage to approximate this problem within any constant factor then P = NP. On the other hand, finding large independent sets is a common subproblem in several graph reduction algorithms and simple heuristics often work very well on the graphs that occur in practice.

This is an important point, but one I feel the article acknowledges well.

There are many impossibility problems that can be solved by relaxing some constraints (like wait-free) or by accepting some unsolvability (we don’t worry too hard about our programs halting in practice, and we generally trust compressed sensing results because the probability of failure is provably delta, say), or just by changing some desiderata.

Great examples include arrows impossibility theorem or the no good clustering result, each of which have solutions if the assumptions that operationalize our intuition are changed slightly.

Or expressed more frankly, try to eat the cooked dinner before it's cooked...

In figure 3, the edge between P0 and Q1 is labeled: "1-simplex (edge) P, R choose 0,2".

Should that be "1-simplex (edge) P, Q choose 0,1"?

Yup. That is correct! I'll get that fixed.

> 19 min read

I do not think so.

Reply on news.ycombinator.com