CSP for binary conservative relational structures

被引:0
作者
Alexandr Kazda
机构
[1] IST Austria,
来源
Algebra universalis | 2016年 / 75卷
关键词
Primary: 08A02; Secondary: 03C05; 68R05; meet-semidistributivity; clone; constraint satisfaction problem; weak near unanimity;
D O I
暂无
中图分类号
学科分类号
摘要
We prove that whenever A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb {A}}$$\end{document} is a 3-conservative relational structure with only binary and unary relations, then the algebra of polymorphisms of A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb {A}}$$\end{document} either has no Taylor operation (i.e., CSP(A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb {A}}$$\end{document}) is NP-complete), or it generates an SD(∧\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\wedge}$$\end{document}) variety (i.e., CSP(A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb {A}}$$\end{document}) has bounded width).
引用
收藏
页码:75 / 84
页数:9
相关论文
共 15 条
[1]  
Atserias A.(2008)On digraph coloring problems and treewidth duality European J. Combin. 29 796-820
[2]  
Bodnarchuk V.(1969)Galois theory for Post algebras. I Cybernetics 5 243-252
[3]  
Kaluzhnin L.(2005)Classifying the complexity of constraints using finite algebras SIAM J. Comput. 34 720-742
[4]  
Kotov V.(1968)Closed systems of functions and predicates Pacific J. Math. 27 95-100
[5]  
Romov B.(2015)Characterizations of several Maltsev conditions Algebra Universalis 73 205-224
[6]  
Bulatov A.(2009)Universal algebra and hardness results for constraint satisfaction problems Theoret. Comput. Sci. 410 1629-1647
[7]  
Jeavons P.(undefined)undefined undefined undefined undefined-undefined
[8]  
Krokhin A.(undefined)undefined undefined undefined undefined-undefined
[9]  
Geiger D.(undefined)undefined undefined undefined undefined-undefined
[10]  
Kozik M.(undefined)undefined undefined undefined undefined-undefined