4 ms·

The Asynchronous Computability Theorem

125 points by heydenberk 9y ago

voidmain 9y ago
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 (?)
- lisper 9y ago
  In particular, impossibility results do not rule out approximate solutions that are good enough for practical purposes.
  - thomasahle 9y ago
    Unless it is an "impossibility of approximation" theorem.
    - fmap 9y ago
      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.
- kevinalexbrown 9y ago
  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.
he0001 9y ago
Or expressed more frankly, try to eat the cooked dinner before it's cooked...
- deleted 9y ago
  [deleted]
Myrmornis 9y ago
> 19 min read I do not think so.
- deleted 9y ago
  [deleted]
ragle 9y ago
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"?
- leog 9y ago
  Yup. That is correct! I'll get that fixed.

125 points by heydenberk 9y ago

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 (?)

lisper 9y ago
In particular, impossibility results do not rule out approximate solutions that are good enough for practical purposes.
- thomasahle 9y ago
  Unless it is an "impossibility of approximation" theorem.
  - fmap 9y ago
    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.
kevinalexbrown 9y ago
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.

he0001 9y ago

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

deleted 9y ago
[deleted]

Myrmornis 9y ago

> 19 min read I do not think so.

deleted 9y ago
[deleted]

ragle 9y ago

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"?

leog 9y ago
Yup. That is correct! I'll get that fixed.