Claremont Algebra/Number Theory/Combinatorics Seminar

Today I am giving the Algebra/Number Theory/Combinatorics Seminar at the Claremont Colleges.  This talk, “What is a #P complete problem” is a prequel in a sense to an earlier talk I gave in the Seminar last year.  In the earlier talk, I discussed new methods for approximating the permanent of a matrix.  In this talk, I will argue that finding the permanent is a hard problem.  One way to characterize hardness of a numerical problem is the notion of  number P problems, or #P for short.  I will define #P problems and give Ben-Dor and Halevi’s 1993 proof that finding the permanent of a matrix is a #P hard problem, so if we could solve it quickly, any problem in #P could also be solved quickly.


, , , ,

  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: