Home | People | Seminar | Working Group | Conferences | Resources


Speaker: Maurice Rojas, Texas A&M

Title: Some Algebraic Characterizations of the P=NP Problem

Abstract: The P=NP problem is the most famous unsolved problem from theoretical computer science and is also one of the biggest unsolved problems in mathematics. (You may recall the million dollar bounty offered by the Clay Institute.)

Many characterizations of the complexity class NP involving logic and combinatorial optimization are known, so we focus on some overlooked characterizations (due to Plaisted) involving the complex roots of polynomials in one variable. We then describe a number-theoretic approach to some of these seemingly geometric problems.

We then conclude with a variant of the P=NP problem (due to Blum, Cucker, Shub, and Smale) and some algebraic characterizations of the latter problem. This variant was introduced with the hopes that a larger part of the arsenal of mathematics (outside of logic and combinatorics) could be brought to bear on P=NP.

We see assume no background in complexity theory.

Return to the seminar page.

Home | People | Seminar | Working Group | Conferences | Resources

Please send comments about this page to Robert Ellis at rellis@math.tamu.edu.
Last Modified on 7/7/03