Number Theory Home | Number Theory Seminar | ArithmeTexas | Department Home
Texas A&M University
Title:A Number-Theoretic Approach to the P vs. NP Problem: I
Abstract: A beautiful result of Pascal Koiran from 1996 revealed that certain plausible assertions on the distribution of prime numbers imply a fast new algorithm for a basic problem from algebraic geometry called FEAS_C: decide whether an arbitrary input system of polynomial equations has a complex root. In particular, Koiran showed that the truth of the Generalized Riemann Hypothesis (GRH) implies the equivalence of the following two statements: (1) P=NP and (2) FEAS_C admits a polynomial algorithm. Thus, in addition to the charming connection between analytic number theory and complex algebraic geometry, Koiran's result shows that one can approach the P vs. NP problem from a new perspective, assuming GRH.
We discuss how the assumption of GRH can be removed under certain conditions, possibly in complete generality. In particular, we begin by reviewing some basic results on the distribution of primes, so we assume no background in complexity theory, number theory, or algebraic geometry.