David Sinclair
School of Computing
Dublin City University

"Computational Complexity, Satisifiability and Verifiaction"

This talk will introduce the key concepts of computational complexity theory
leading up to the distinction between the classes P and NP. The satisfiability
problem will be introduced and its key role computational complexity will be
discussed. Approaches to solving very large satisfiability problems will be
examined. As an example of application areas, system verifiaction, bounded
model checking and unbounded model checking will be discussed.