Computer Science/Discrete Mathematics Seminar II

As solutions can be efficiently verified, any NP-complete problem can be solved by exhaustive search. Unfortunately, even for small instances the running time for exhaustive search becomes very high. 

On the bright side, for many NP-complete problems it is possible to design significantly faster algorithms, though still not polynomial time. 

Such algorithms were extensively explored, even a decade before the definition of NP. By now we have non-trivial running times for many problems including satisfiability, graph coloring, knapsack, TSP, maximum independent sets and more.

In this talk, we will mostly focus on new algorithms for the graph coloring problem.