Speaker:  Sue Coppersmith, Univ. of Wisconsin

Title: Dynamical systems, computational complexity, and the P versus NP question

Abstract: The question of whether or not P is equal to NP is a long-standing open problem in computer science. P is the class of problems that can be solved in polynomial time (time that grows no faster than polynomially with the size of the problem specification), and NP is the class of problems for which a solution can be verified in polynomial time. This talk will argue that the study of the physics of specific dynamical systems problems may facilitate the resolution of this question. Strong evidence is presented that P is not equal to NP.

HOME