BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260726T073408Z
UID:Seminar-dept-1031@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20230131T130000
DTEND:20230131T140000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Tony Tan: DQBF is a CNF formula in succinct representation\n\nThe satisfiability of Dependency Quantified Boolean Formulas (DQBFs) recently has attracted a lot of attention in SAT community. Intuitively DQBF is the extension of QBF where for each existentially quantified variable,\n\none can specify its set of dependent variables.\n\n\n\nIn this talk we will show that a DQBF is simply a CNF formula in an exponentially more succinct representation.\n\nFor a positive integer k, a k-DQBF is a DQBF with k existentially quantified variables.\n\nWe show the following.\n\n1) k-DQBF is a succinct representation of a k-CNF formula.\n\n2) The satisfiability of 2-DQBFs and 3-DQBFs is PSPACE-complete and NEXP-complete, resp.\n\n3) A parsimonious polynomial time reduction from DQBFs to 3-DQBFs.\n\n4) Natural explicit reductions from well known NEXP-complete problems to the satisfiability of DQBF.\n\n\n\nResults (2)--(4) parallel the following well known classical results for SAT.\n\n*) The satisfiability of 2-CNF and 3-CNF formulas is NLOG-complete and NP-complete, resp.\n\n*) A parsimonious polynomial time reduction from arbitrary boolean formulas to 3-CNF formulas.\n\n*) Natural reductions (in the form of Cook-Levin reductions) from NP-complete problems to SAT.\n\n\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1031
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR