UIC Graduate Student Seminar

Friday April 20
3:00 pm
636 SEO

Speaker: Gyorgy Turan

Title: Propositional logic and complexity

Abstract: A conjunctive normal form (CNF) expression in propositional logic is an `and' of `or's of negated and unnegated variables, such as (x or not(y)) and (not(x) or z). The satisfiability problem is the following: given a CNF expression, can we assign `true' or `false' to the variables to make the expression true? This can be answered by checking all possible truth assignments, but for n variables there are 2^n of these, so that approach is not feasible. The question whether there is an efficient algorithm for the satisfiability problem is one of the outstanding open problems. Another related question is that, given an unsatisfiable CNF expression, is there a short proof of its unsatisfiability? We plan to give an overview of some of the results related to these questions.