Infosecurity.US

Information Security & Occasional Forays Into Adjacent Realms

  • Web Log
maxresdefault.jpg

Limits of Computation →

October 23, 2015 by Marc Handelman in ACM, All is Information, Computation

John Pavlus, writing at Quanta Magazine regales us with the story of a 'Solution That Doesn't Exist'.

Yet in a paper presented at the ACM Symposium on Theory of Computing, two researchers from the Massachusetts Institute of Technology put forth a mathematical proof that the current best algorithm was “optimal” — in other words, that finding a more efficient way to compute edit distance was mathematically impossible. The Boston Globe celebrated the hometown researchers’ achievement with a headline that read “For 40 Years, Computer Scientists Looked for a Solution That Doesn’t Exist.”

October 23, 2015 /Marc Handelman
ACM, All is Information, Computation
  • Newer
  • Older