All Media Types
Fifty years of P vs. NP and the possibility of the impossible
Fortnow L. Communications of the ACM 65(1): 76-85, 2022. Type: Article
The P versus NP problem is one of the most fundamental and well-known unresolved questions in computer science. In comparison with the 2009
article by the same author , the current survey is less about progress toward a so...
Jun 27 2022
Fortnow L., Goldsmith J., Mahaney S., Levy M. SIAM Journal on Computing 28(1): 137-151, 1998. Type: Article
One of the central questions of complexity theory is whether polynomial-time computations can do something that logarithmic space-bounded computations cannot do. The typical framework for this question is language recognition, specifically, the DL...
Oct 1 1999
Reproduction in whole or in part without permission is prohibited. Copyright © 2000-2022 ThinkLoud, Inc.