Seminars and Colloquiums
for the week of November 19, 2007
Speakers:
Mr. Masato Kobayashi, Tuesday
Dr. Jim Conant, Tuesday
Tuesday, November 20
ALGEBRA SEMINAR
TIME: 2:10 – 3:00
ROOM: 309B Ayres
SPEAKER: Mr. Masato Kobayashi
TITLE: "D + M" factorization properties
COLLOQUIUM ** TUESDAY, November 20 **
TIME: 3:40
ROOM: 214 Ayres
SPEAKER: Professor Jim Conant
TITLE: The Topology of Sets of Boolean Formulae
ABSTRACT: The k-SAT problem in computer science asks whether a given formula in a specified canonical form (a conjunction of disjunctions of k literals) can be satisfied by some assignment of truth values to the variables. It is well known that the 2-SAT problem can be solved in polynomial time, whereas the 3-SAT problem is NP-complete. The set of satisfiable formulae in k-SAT is a poset under logical implication, and in this talk we will study the topology of this poset. The goal of the project is to find topological differences between 2-SAT and 3-SAT with an eye toward separating the classes of P and NP problems. At this stage, the general topological beha
Previous Announcements:
Week of:
Seminars from 2006-2007 academic year