Number Theory Home | Number Theory Seminar | ArithmeTexas | Department Home
Texas A & M
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.