MATH 8714: Topics in Logic

Spring 2015

MWF 12:00-12:50 pm, HUMN 335

Syllabus

Course description: The course will focus on the following problem:

How difficult is it to decide if an existential second order sentence is true in a structure?

This problem has connections to logic, combinatorics, algebra, and computer science. Examples include:

testing if a set of linear equations is consistent;
testing if a graph is 3-colorable;
testing if a group has a nontrivial normal subgroup;
testing if two graphs are isomorphic.

The first major topic of the course will be R. Fagin's theorem which states that a class C of finite structures is defined by an existential second order sentence if and only if membership in C can be determined in NP (non-deterministic polynomial time). Next, we will talk about work of T. Feder and M. Vardi which isolates a subclass of these problems, called Constraint Satisfaction Problems, for which they conjecture that the time complexity of deciding membership is either in P (polynomial time) or NP-complete (as hard as possible in NP); that is, no intermediate complexity occurs. Finally, we will discuss what is currently known about this conjecture.

Assignments: You will be asked to give short presentations in class, and there will be several homework assignments during the semester. You will be asked to submit solutions to homework problems in pdf. When in final form, solutions will be posted. You should read your classmates' solutions.
For some of the assignments you may be asked to work in small groups.

Getting Help: Don't wait until it is too late if you need help.

Ask questions!

I am available during my office hours and many other times. If you can't see me during office hours, then make an appointment with me to see me at a different time.

Campus Policies: By clicking on `Campus Policies' in the left panel at the top of this page you will find details about

the honor code,
the campus policies on classroom behavior, on accommodating students with disabilities, and on observance of religious holidays, and
the campus policies on discrimination and harassment, sexual harassment, and amorous relationships.

If you need any special accommodation due to medical disability or observance of a religious holiday, please inform me as soon as possible (preferably within the first two weeks of class), and provide documentation.