Back to full Calendar
AMCS Seminar: Boundary Properties...
Start Date: December 21, 2011
End Date: December 21, 2011
Boundary Properties of the Satisfiability Problems
By
Dr. Vadim Lozin (University of Warwick, UK)
The satisfiability problem is known to be NP-complete in general and for many restricted instances, such as formulas with at most 3 variables per clause and at most 3 occurrences per variable, or planar formulas. The latter example refers to graphs representing satisfiability instances. These are bipartite graphs with vertices representing clauses and variables, and edges connecting variables to the clauses containing them.Finding the strongest possible restrictions under which a problem remains NP-complete is important for at least two reasons. First, this can make it easier to establish the NP-completeness of new problems by allowing easier transformations. Second, this can help clarify the boundary between tractable and intractable instances of the problem. In this talk, we address the second issue and reveal the first boundary property of graphs representing satisfiability instances.
Biography: Vadim Lozin received his Ph.D. in Theoretical Computer Science in 1995 from the University of Nizhny Novgorod, Russia. In 2000, he moved to Rutgers University (USA) and in 2007, to the University of Warwick (UK), where he now is an Associate Professor of Mathematics. He is an author of more than 80 publications in the area of graph theory, combinatorics and discrete mathematics. He is an Associate Editor of the journal "Discrete Applied Mathematics".
| Date & Time: Wednesday, December 21st, 2011 from 03:00 pm to 04:00 pm Location: Room # 3119, level 3, building 1 (Al-Khwarizmi) Refreshments: Available in 3119 @ 02:45 pm |
For more information:
Contact: Mikhail Moshkov
Email: Mikhail.Moshkov@kaust.edu.sa
Phone:
Cell:
Website:
