License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2011.3
URN: urn:nbn:de:0030-drops-33580
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3358/
Go to the corresponding LIPIcs Volume Portal

Vardi, Moshe Y.

Constraints, Graphs, Algebra, Logic, and Complexity (Invited Talk)

pdf-format:
40.pdf (0.2 MB)

Abstract

A large class of problems in AI and other areas of computer science can be viewed as constraint-satisfaction problems. This includes problems in database query optimization, machine vision, belief maintenance, scheduling, temporal reasoning, type reconstruction, graph theory, and satisfiability. All of these problems can be recast as questions regarding the existence of homomorphisms between two directed graphs. It is well-known that the constraint-satisfaction problem is NP-complete. This motivated an extensive research program into identify tractable cases of constraint satisfaction.
This research proceeds along two major lines. The first line of research focuses on non-uniform constraint satisfaction, where the target graph is fixed. The goal is to identify those target graphs that give rise to a tractable constraint-satisfaction problem. The second line of research focuses on identifying large classes of source graphs for which constraint-satisfaction is tractable. We show in how tools from graph theory, universal algebra, logic, and complexity theory, shed light on the tractability of constraint satisfaction.

BibTeX - Entry

@InProceedings{vardi:LIPIcs:2011:3358,
  author =	{Moshe Y. Vardi},
  title =	{{Constraints, Graphs, Algebra, Logic, and Complexity (Invited Talk)}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{3--3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Supratik Chakraborty and Amit Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3358},
  URN =		{urn:nbn:de:0030-drops-33580},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.3},
  annote =	{Keywords: constraint satisfaction, NP completeness, dichotomy}
}

Keywords: constraint satisfaction, NP completeness, dichotomy
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Issue Date: 2011
Date of publication: 01.12.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI