BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260920T212334Z
UID:Seminar-verification-1190@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Patrick Totzke:MAILTO:totzke@liverpool.ac.uk
DTSTART:20231102T110000
DTEND:20231102T120000
SUMMARY:Verification Series
DESCRIPTION:Tony Tan: Towards a more efficient approach to NEXP-complete problems\n\nMany NEXP-complete problems have algorithms that are elegant in theory, but not so practical. For example, the satisfiability of two-variable fragment of first-order logic is a well known NEXP-complete problem. However, for more than 2 decades the only known algorithm works as follows: On input formula F, guess an exponential size model and verify that it satisfies F.\n\n\n\nObviously, there is a lot of room for improvement.\n\n\n\nI will describe this talk into two parts: In the first part I will briefly describe some of the recent work on two-variable logic. In the second part I will discuss Dependency Quantified Boolean Formula (DQBF) and its strong correlation with SAT which makes it an ideal candidate as the problem in the class NEXP, just like SAT is the problem in the class NP.\n\n\n\n\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1190
LOCATION:
END:VEVENT
END:VCALENDAR