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
Abstract:
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