**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.