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 条

[1]

[Anonymous], 2004, ELECT C COMPUTATIONA, DOI [DOI 10.1145/1060590.1060647, 10.1145/1060590.1060647]

[2] Constraint Satisfaction Problems of Bounded Width [J].

Barto, Libor ;

Kozik, Marcin .

2009 50TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: FOCS 2009, PROCEEDINGS, 2009, :595-603

[3]

BODIRSKY M, 2006, LECT NOTES COMPUT SC, V4207

[4] The complexity of equality constraint languages [J].

Bodirsky, Manuel ;

Kara, Jan .

THEORY OF COMPUTING SYSTEMS, 2008, 43 (02) :136-158

[5] Constraint satisfaction with countable homogeneous templates [J].

Bodirsky, Manuel ;

Nesetril, Jaroslav .

JOURNAL OF LOGIC AND COMPUTATION, 2006, 16 (03) :359-373

[6] THE REDUCTS OF EQUALITY UP TO PRIMITIVE POSITIVE INTERDEFINABILITY [J].

Bodirsky, Manuel ;

Chen, Hubie ;

Pinsker, Michael .

JOURNAL OF SYMBOLIC LOGIC, 2010, 75 (04) :1249-1292

[7]

Börner F, 2003, LECT NOTES COMPUT SC, V2803, P58

[8] Classifying the complexity of constraints using finite algebras [J].

Bulatov, A ;

Jeavons, P ;

Krokhin, A .

SIAM JOURNAL ON COMPUTING, 2005, 34 (03) :720-742

[9] Tractable conservative constraint satisfaction problems [J].

Bulatov, AA .

18TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS, 2003, :321-330

[10] A simple algorithm for Mal'tsev constraints [J].

Bulatov, Andrei ;

Dalmau, Victor .

SIAM JOURNAL ON COMPUTING, 2006, 36 (01) :16-27

← 1 2 3 →