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.