QUANTIFIED EQUALITY CONSTRAINTS

被引：13

作者：

Bodirsky, Manuel ^{[1
]}

Chen, Hubie ^{[2
]}

机构：

[1] Ecole Polytech, Lab Informat, LIX, CNRS,UMR 6171, F-75010 Paris, France

[2] Univ Pompeu Fabra, Dept Tecnol Informacio & Comunicac, Barcelona 08003, Spain

来源：

SIAM JOURNAL ON COMPUTING | 2010年 / 39卷 / 08期

关键词：

quantified constraint satisfaction; omega-categorical structures; computational complexity; SATISFACTION; TRACTABILITY;

D O I：

10.1137/080725209

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

An equality template is a relational structure with infinite universe whose relations can be defined by Boolean combinations of equalities. We prove a complexity classification for quantified constraint satisfaction problems (QCSPs) over equality templates: These problems are in L (decidable in logarithmic space), NP-hard, or coNP-hard. To establish our classification theorem we combine methods from universal algebra with concepts from model theory.

引用

页码：3682 / 3699

页数：18

共 27 条

[11]

Creignou N., 2001, SIAM MONOGR DISCRETE, V7

[12]

Garey Michael, 1978, GUIDE NP COMPLETENES

[13] FINITE CLONES CONTAINING ALL PERMUTATIONS [J].

HADDAD, L ;

ROSENBERG, IG .

CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 1994, 46 (05) :951-970

[14]

HELL P, 2004, SER MATH APPL, V28

[15]

Hodges W., 1997, SHORTER MODEL THEORY

[16] Tractability and learnability arising from algebras with few subpowers [J].

Idziak, Pawel ;

Markovic, Petar ;

McKenzie, Ralph ;

Valeriote, Matthew ;

Willard, Ross .

22ND ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS, 2007, :213-+

[17] On the algebraic structure of combinatorial problems [J].

Jeavons, P .

THEORETICAL COMPUTER SCIENCE, 1998, 200 (1-2) :185-204

[18] Closure properties of constraints [J].

Jeavons, P ;

Cohen, D ;

Gyssens, M .

JOURNAL OF THE ACM, 1997, 44 (04) :527-548

[19] REDUCED PRODUCTS AND HORN CLASSES [J].

KEISLER, HJ .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1965, 117 (05) :307-&

[20] On tractability and congruence distributivity [J].

Kiss, Emil ;

Valeriote, Matthew .

21ST ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS, 2006, :221-+

← 1 2 3 →