|
 |
 Courtesy of xkcd.com
|
What are the ultimate limits on what can feasibly be computed in the physical world? In this talk, I'll try to show how this question ties together many of the central concerns of math, computer science, and physics. I'll also explain how research in quantum computing has transformed our understanding of the question over the last fifteen years. Finally, I'll offer a concrete conjecture—that there is no physical means to solve certain computationally complex problems (NP-complete)—and discuss the evidence for this conjecture, as well as the implications for physics if it's accepted.
Anyone outside NIST wishing to attend must be sponsored by a NIST employee and receive a visitor badge. For more information, call Kum J. Ham at 301-975-4203.
Colloquia are videotaped and available in the NIST Research Library.