Attacking very hard problems
- Speaker: Dr Oliver Kullman, Dept of Computer Science, Swansea University
- Date: Tuesday, 16 May 2017 from 17:00 to 18:00
- Location: Room 151
In my talk I will outline "theory and practice" of attacking very hard
*concrete* problems in the neighbourhood of NP, via SAT solving and
other related tools, exploiting massive computations.
On the problem side, I will focus on problems from Ramsey theory, where
on the one hand a rich theory is available, and where, perhaps
surprisingly, on the other hand the problems show some strong similarities to
Concerning algorithms, I will outline the Cube-and-Conquer paradigm, a
hybrid scheme for SAT solving. This will prompt the need for a "hybrid"
complexity theory, employing oracles, and leveraging the advantages of
trees *and* dags.