| Title: | Random Hard Problems |
| Speaker: | Harold S. Connamacher Assistant Professor Mathematics and Computer Science Albion College Albion, Michigan |
| Abstract: | If it is easy to verify the solution to a problem, is it easy to solve that problem? This is the famous P vs NP problem. There are other important open questions we can ask. Is a uniformly randomm instance of a hard to solve problem still hard to solve? Are there specific structures in the solution space to a problem that will prevent certain algorithm techniques from working? This talk explores what is currently known about these questions, and we will use the well-known problems 3-SAT and factoring as examples. The talk will also introduce some new work in defining a random problem model that has many of the properties of 3-SAT but for which we can prove behavior that we observe experimentally but not yet prove for 3-SAT. |
| Location: | Palenske 227 |
| Date: | 9/30/2010 |
| Time: | 3:10 |
@abstract{MCS:Colloquium:HaroldSConnamacher:2010:9:30,
author = "{Harold S. Connamacher}",
title = "{Random Hard Problems}",
address = "{Albion College Mathematics and Computer Science Colloquium}",
month = "{30 September}",
year = "{2010}"
}