Mordechai Rorvig in Quanta:
Last summer, three researchers took a small step toward answering one of the most important questions in theoretical computer science. To paraphrase Avi Wigderson of the Institute for Advanced Study, that question asks something simple but profound: Can we solve all the problems we hope to solve?
More precisely, computer scientists want to know whether all the problems we hope to solve can be solved efficiently, in a reasonable amount of time — before the end of the universe, say. If not, they are simply far too difficult.
Many problems seem to be this hard, but we won’t know for certain until we can mathematically prove their difficulty. And in a paper from last year, a trio of computer scientists showed that a broad category of problems are indeed too difficult to be solved efficiently, thereby providing one of the best examples yet of what the field has been seeking.
More here.