Albion College

Mathematics and Computer Science

Mathematics and Computer Science

COLLOQUIUM

Random Hard Problems

Harold S. Connamacher

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.