David Hilbert’s program proposed to ground all mathematical theories to a single simple system. One of the properties of such a system that Hilbert deemed desirable was “Decidability”. While Hilbert’s program was shown to be impossible to achieve by Gödel (and later Turing), several interesting and non-trivial theories exist for which algorithms have been found! In this talk, we will mention some of them. First, we will focus on propositional logic, its satisfiability problem and its connection to the P vs NP question, as well as its (previously unthinkable) practical applications. Then, we will mention a few other theories of interest which are known to be decidable.

This talk is partially based on Moshe Vardi’s talk “The SAT Revolution: Solving, Sampling, and Counting”.

You can watch a recording of the seminar talk here

Speaker

Guillermo A. Perez is assistant professor at the Department of Computer Science. His research concerns logic and automata theory, formal verification of software and hardware, as well as learning theory.

Time and Place

Friday 7/10/2022 at 11:30am in M.A.143

Registration

Participation is free, but registration is compulsory. Make sure to fill in this form.

References and Related Reading

  • What is automata?
    • Introduction to the Theory of Computation (Book), Michael Sipser
    • Theory of Computation (Book), Dexter Kozen
    • Talen en Automaten (Course)
  • What is mathematical logic? What are its applications?
    • Discrete Mathematics (Course)
    • Toegepaste Logica (Course)
    • Wiskundige Logica (Course)
    • Specification and Verification (Course)
  • What is (un)decidability? Complexity?
    • Machines en Berekenbaarheid (Course)
    • Algorithms and Complexity (Course)
  • Fun links
    • M. Vardi’s talk
    • The Golden Ticket P, NP, and the Search for the Impossible (Book), Lance Fortnow
    • Logicomix: An Epic Search for Truth (Book), Apostolos Doxiadis and Christos H. Papadimitriou