Department of

Mathematics


Seminar Calendar
for events the day of Wednesday, February 20, 2019.

     .
events for the
events containing  

(Requires a password.)
More information on this calendar program is available.
Questions regarding events or the calendar should be directed to Tori Corkery.
     January 2019          February 2019            March 2019     
 Su Mo Tu We Th 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 22 23 24 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

4:00 pm in 245 Altgeld Hall,Wednesday, February 20, 2019

Connecting Boolean (un)satisfiability to Graph Theory

Vaibhav Karve (Illinois Math)

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.