Vardi, Moshe Y.
Constraints, Graphs, Algebra, Logic, and Complexity (Invited Talk)
Abstract
A large class of problems in AI and other areas of computer science can be viewed as constraintsatisfaction 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 wellknown that the constraintsatisfaction problem is NPcomplete. 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 nonuniform constraint satisfaction, where the target graph is fixed. The goal is to identify those target graphs that give rise to a tractable constraintsatisfaction problem. The second line of research focuses on identifying large classes of source graphs for which constraintsatisfaction 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 = {33},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897347},
ISSN = {18688969},
year = {2011},
volume = {13},
editor = {Supratik Chakraborty and Amit Kumar},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3358},
URN = {urn:nbn:de:0030drops33580},
doi = {10.4230/LIPIcs.FSTTCS.2011.3},
annote = {Keywords: constraint satisfaction, NP completeness, dichotomy}
}
2011
Keywords: 

constraint satisfaction, NP completeness, dichotomy 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Issue date: 

2011 
Date of publication: 

2011 