Campus Event Calendar
Event Entry
What and Who
The Difficulty of Achieving (Abstract) Satisfaction
Martin Brain
University of Oxford
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI
Public Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 29 September 2016
14:00
60 Minutes
Warning: Date has changed!
E1 4
024
Saarbrücken
Abstract
A small amount of practical experience with SAT, SMT or CSP solvers (or
any tool that uses them, such as most verification systems) will show
that there is significant variation in run-time even between relatively
similar problems. This naturally leads to a whole range of questions;
What is difficulty? Where does it come from? What is the relation
between theoretical measures (such as proof complexity) and practical
ones (such as run-time)? Can we recognise difficulty and identify it
with parts of the problem? Can we predict the difficulty of a problem
in less time than it takes to solve it? In this talk we will present an
abstract satisfaction view on difficulty; using the mathematics of
abstract interpretation to understand satisfiability problems. This is
a work-in-progress talk so all are welcome to attend and participate.
any tool that uses them, such as most verification systems) will show
that there is significant variation in run-time even between relatively
similar problems. This naturally leads to a whole range of questions;
What is difficulty? Where does it come from? What is the relation
between theoretical measures (such as proof complexity) and practical
ones (such as run-time)? Can we recognise difficulty and identify it
with parts of the problem? Can we predict the difficulty of a problem
in less time than it takes to solve it? In this talk we will present an
abstract satisfaction view on difficulty; using the mathematics of
abstract interpretation to understand satisfiability problems. This is
a work-in-progress talk so all are welcome to attend and participate.
Contact
Jennifer Müller
2900
--email hidden
passcode not visible
logged in users only
Jennifer Müller, 09/27/2016 14:58
Jennifer Müller, 09/13/2016 11:19 -- Created document.
Jennifer Müller, 09/13/2016 11:19 -- Created document.