DagSemProc.09441.4.pdf
- Filesize: 246 kB
- 15 pages
Document
PP-DEFINABILITY IS CO-NEXPTIME-COMPLETE
Author
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 9441
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2010-01-07
Cite As Get BibTex
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)
https://doi.org/10.4230/DagSemProc.09441.4
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.
Subject Classification
Keywords
- Primitive positive formula
- definability
- complexity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads