Department of

January 2019February 2019 March 2019 Su Mo TuWeTh Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 4 5 1 2 1 2 6 7 8 9 10 11 12 3 4 5 6 7 8 9 3 4 5 6 7 8 9 13 14 15 16 17 18 19 10 11 12 13 14 15 16 10 11 12 13 14 15 16 20 21 222324 25 26 17 18 19 20 21 22 23 17 18 19 20 21 22 23 27 28 29 30 31 24 25 26 27 28 24 25 26 27 28 29 30 31

Wednesday, February 20, 2019

**Abstract:** Given a Boolean formula can we find consistent assignments (True or False)for variables such that the formula is satisfied? This is the Boolean Satisfiability problem, a problem of great historic value in computer science. It is the first problem that was proven to be NP-complete. In this talk, I will introduce Satisfiability and explain what the terms P, NP, NP-complete... mean. I will then demonstrate a (surprising)connection between Boolean formulas and graph theory which will help us gain a more visual understanding of when a class of formulas is satisfiable or unsatisfiable. There will be lots of small graphs in this talk.