License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-23680
URL: https://drops.dagstuhl.de/opus/volltexte/2010/2368/
Go to the corresponding Portal |
Willard, Ross
PP-DEFINABILITY IS CO-NEXPTIME-COMPLETE
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.
BibTeX - Entry
@InProceedings{willard:DSP:2010:2368,
author = {Ross Willard},
title = {PP-DEFINABILITY IS CO-NEXPTIME-COMPLETE},
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 = {1862-4405},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2368},
annote = {Keywords: Primitive positive formula, definability, complexity}
}
Keywords: |
|
Primitive positive formula, definability, complexity |
Collection: |
|
09441 - The Constraint Satisfaction Problem: Complexity and Approximability |
Issue Date: |
|
2010 |
Date of publication: |
|
07.01.2010 |