Willard, Ross
PPDEFINABILITY IS CONEXPTIMECOMPLETE
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 coNExpTime,
and has been shown to be tractable on the boolean domain.
We show that there exists $k>2$ such that $exists$InvSat is
coNExpTime complete on $k$element domains, answering a
question of Creignou, Kolaitis and Zanuttini.
BibTeX  Entry
@InProceedings{willard:DSP:2010:2368,
author = {Ross Willard},
title = {PPDEFINABILITY IS CONEXPTIMECOMPLETE},
booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability},
year = {2010},
editor = {Andrei A. Bulatov and Martin Grohe and Phokion G. Kolaitis and Andrei Krokhin},
number = {09441},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2368},
annote = {Keywords: Primitive positive formula, definability, complexity}
}
2010
Keywords: 

Primitive positive formula, definability, complexity 
Seminar: 

09441  The Constraint Satisfaction Problem: Complexity and Approximability

Related Scholarly Article: 


Issue date: 

2010 
Date of publication: 

2010 