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