PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Stephen Simpson.

Title:Translating combinatorial problems into propositional calculus.
Seminar:Logic Seminar
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

Room Number:MB216
Date:08 / 26 / 2008
Time:02:30pm - 03:45pm