For more information about this meeting, contact Stephen Simpson.
|Title:||Translating combinatorial problems into propositional calculus.|
|Speaker:||Stephen G. Simpson, Pennsylvania State University|
|We present some illustrations of how to translate combinatorial problems into formulas of the propositional calculus. For example, we show how to associate to each finite graph G a propositional formula A_G such that G is Hamiltonian if and only if A_G is satisfiable. We discuss how such translations are useful in a variety of contexts, including the P = NP problem and certain problems of infinitary combinatorics.|
Room Reservation Information
|Date:||08 / 26 / 2008|
|Time:||02:30pm - 03:45pm|