2 ms·
NP-Complete Problems and Physical Reality (2005) [pdf]
- weinzierl 11y agoThis has already been discussed on HN[1]. There have been some minor updates to the paper, here is the diff: < are the gear-based computers of Vergis, Steiglitz, Dickinson , and > are the gear-based computers of Vergis, Steiglitz, and Dickinson , and < (called Steiner vertices) other than the pegs themselves. Garey, > (called Steiner vertices) other than the points themselves. Garey, < spacetimes cannot be globally hyperbolic; that is to say, they must > spacetimes cannot be globally hyperbolic; for example, they could < a polynomial number of bits (or qubits) around that curve. Bacon > a polynomial number of bits (or qubits) around that CTC. Bacon < I thank Al Aho, Pioter Drubetskoy, Daniel Gottesman, David Poulin, < John Preskill, and others who I have undoubtedly forgotten for < enlightening conversations about the subject of this article. I < especially thank Dave Bacon, Dan Christensen, and Antony Valentini < for critiquing a draft, and Lane Hemaspaandra for pestering me to < finish the damn thing. > I thank Al Aho, Pioter Drubetskoy, Daniel Gottesman, Klas Markstrom, > David Poulin, John Preskill, and others who I have undoubtedly > forgotten for enlightening conversations about the subject of this > article. I especially thank Dave Bacon, Dan Christensen, and Antony > Valentini for critiquing a draft, and Lane Hemaspaandra for pestering > me to finish the damn thing. [1] https://news.ycombinator.com/item?id=8942220 https://news.ycombinator.com/item?id=8942220