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