DROPS

Document

Polymorphisms, and How to Use Them

Authors: Libor Barto, Andrei Krokhin, and Ross Willard

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)

Abstract

This article describes the algebraic approach to Constraint Satisfaction Problem that led to many developments in both CSP and universal algebra. No prior knowledge of universal algebra is assumed.

Cite as

Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and How to Use Them. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 1-44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InCollection{barto_et_al:DFU.Vol7.15301.1,
  author =	{Barto, Libor and Krokhin, Andrei and Willard, Ross},
  title =	{{Polymorphisms, and How to Use Them}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{1--44},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.1},
  URN =		{urn:nbn:de:0030-drops-69595},
  doi =		{10.4230/DFU.Vol7.15301.1},
  annote =	{Keywords: Constraint satisfaction, Complexity, Universal algebra, Polymorphism}
}

Document

DOI: 10.4230/DagSemProc.09441.4

PP-DEFINABILITY IS CO-NEXPTIME-COMPLETE

Authors: Ross Willard

Published in: Dagstuhl Seminar Proceedings, Volume 9441, The Constraint Satisfaction Problem: Complexity and Approximability (2010)

Abstract

$exists$-InvSat is the problem which takes as input a relation $R$ and a finite set $mathcal S$ of relations on the same finite domain $D$, and asks whether $R$ is definable by a conjunctive query over $mathcal S$, i.e., by a formula of the form $exists mathbf{y} varphi(mathbf{x},mathbf{y})$ where $varphi$ is a conjunction of atomic formulas built on the relations in $mathcal S cup {=}$. (These are also called emph{primitive positive formulas}.) The problem is known to be in co-NExpTime, and has been shown to be tractable on the boolean domain. We show that there exists $k>2$ such that $exists$-InvSat is co-NExpTime complete on $k$-element domains, answering a question of Creignou, Kolaitis and Zanuttini.

Cite as

Ross Willard. PP-DEFINABILITY IS CO-NEXPTIME-COMPLETE. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Seminar Proceedings, Volume 9441, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{willard:DagSemProc.09441.4,
  author =	{Willard, Ross},
  title =	{{PP-DEFINABILITY IS CO-NEXPTIME-COMPLETE}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9441},
  editor =	{Andrei A. Bulatov and Martin Grohe and Phokion G. Kolaitis and Andrei Krokhin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09441.4},
  URN =		{urn:nbn:de:0030-drops-23680},
  doi =		{10.4230/DagSemProc.09441.4},
  annote =	{Keywords: Primitive positive formula, definability, complexity}
}

Search Results

Documents authored by Willard, Ross

Polymorphisms, and How to Use Them

Abstract

Cite as

PP-DEFINABILITY IS CO-NEXPTIME-COMPLETE

Abstract

Cite as

Thanks for your feedback!

Could not send message