Computational Complexity of Quantified Constraint Satisfaction Problems

  • 1 November 2019
  • 14:00 - 15:00
  • N112

Presented By Catarina Carvalho/L Nagel

Abstract

In 1998 it was shown that a Constraint Satisfaction Problem (CSP) can be viewed as the problem of finding a homomorphism between relational structures, establishing the link between constraint satisfaction and universal algebra. In 2017, using algebraic methods, the widely studied CSP dichotomy conjecture, that says that a CSP is either in P or NP-complete, was proved. The quantified generalisation of the CSP, QCSP, is now left as the last of the older variants of the CSP to have been widely studied but not yet classified.

We will present an overview of what is known about the computational complexity of the QCSP, and present some algebraic tools that have been helpful in this study.

Biography

Catarina Carvalho is a Senior Lecturer in Mathematics in the School of Physics, Astronomy and Mathematics and the University of Hertfordshire.

She obtained her PhD from St Andrews in the are of Algebra, and went on to take postdoctoral positions in Computer Science at Durham University and Simon Fraser University. She also held a Postdoctoral Fellowship and the University of Lisbon before starting her position at Herts. Her current area of research is mainly on algebraic aspects of computational complexity, in particular in connections withConstraint Satisfaction Problems and its variations.

Contact and booking details

Booking required?
No