Number Theory Home | Number Theory Seminar | ArithmeTexas | Department Home

Texas A&M Number Theory Seminar

Department of Mathematics
Milner 216
Wednesdays, 1:45-2:45 PM

Maurice Rojas

Texas A & M

Wednesday, January 30, 2008

Milner 216, 1:45PM

Title: A Number-Theoretic Approach to the P vs. NP Problem: II

Abstract:Last week, in Part I, we saw how (assuming GRH) one can try to prove that P is not equal to NP by proving that complex feasibility does not admit a polynomial-time algorithm. (While the latter task is not easy, it is an approach which should be compared with Mulmuley and Sohoni's approach via representation theory.) We also saw a sketch of Koiran's algorithm, which uses the density of certain sets of primes (and the truth of GRH) to check whether an input polynomial system has complex roots.

In this lecture, we explore quantitative estimates on various prime-counting functions, and how they allow one to weaken or remove the assumption of GRH above. As before, we assume no background in complexity theory, number theory, or algebraic geometry.