Colloquium Details
Yes/No Satisfiability: Close to the Edge of NP-Completeness
| Author: | Jan Kratochvil Charles University, Prague |
|---|---|
| Date: | January 13, 2000 |
| Time: | 16:00 |
| Location: | 220 Deschutes |
Abstract
Satisfiability of Boolean formulas is one of the most important NP-complete problems. Both for being actually the first identified NP-complete problem, and for its practical applications. By the latter meaning solving and approximating certain optimization problems as well as showing NP-completeness of others.
For any difficult problem, it is always useful to study various restrictions to understand the borderline between NP-complete and polynomially solvable instances. In the talk I will survey several such restrictions and demonstrate their applications. Issues such as bounding the number of occurrences of variables or planarity will be considered, and several variants of satisfiability (1-in-3, Not-all-equal).