EUVIMEDEUVIMED entdecken
Crossref

Sandwiches for promise constraint satisfaction

Guofeng Deng, Ezzeddine El Sai, Trevor Manders, Peter Mayr, Poramate Nakkirt, Athena Sparks

Algebra universalis · 2021-02 · 82 (1)

DOI: 10.1007/s00012-020-00702-5 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algebra universalis, online erschienen am 20.01.2021. Verfasst von Guofeng Deng und 5 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 9 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Promise Constraint Satisfaction Problems (PCSP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm{PCSP}$$\end{document}) were proposed recently by Brakensiek and Guruswami as a framework to study approximations for Constraint Satisfaction Problems (CSP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm{CSP}$$\end{document}). Informally a PCSP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm{PCSP}$$\end{document} asks to distinguish between whether a given instance of a CSP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm{CSP}$$\end{document} has a solution or not even a specified relaxation can be satisfied. All currently known tractable PCSP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm{PCSP}$$\end{document}s can be reduced in a natural way to tractable CSP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm{CSP}$$\end{document}s. In 2019 Barto presented an example of a PCSP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm{PCSP}$$\end{document} over Boolean structures for which this reduction requires solving a CSP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm{CSP}$$\end{document} over an infinite structure. We give a first example of a PCSP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm{PCSP}$$\end{document} over Boolean structures which reduces to a tractable CSP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm{CSP}$$\end{document} over a structure of size 3 but not smaller. Further we investigate properties of PCSP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm{PCSP}$$\end{document}s that reduce to systems of linear equations or to CSP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm{CSP}$$\end{document}s over structures with semilattice or majority polymorphism.

Zitieren

APA

Deng, G., Sai, E. E., Manders, T., Mayr, P., Nakkirt, P., & Sparks, A. (2021). Sandwiches for promise constraint satisfaction. Algebra universalis, 82(1). https://doi.org/10.1007/s00012-020-00702-5

Vancouver

Deng G, Sai EE, Manders T, Mayr P, Nakkirt P, Sparks A. Sandwiches for promise constraint satisfaction. Algebra universalis. 2021;82(1). doi:10.1007/s00012-020-00702-5

BibTeX
@article{Deng2021,
  author = {Deng, Guofeng and Sai, Ezzeddine El and Manders, Trevor and Mayr, Peter and Nakkirt, Poramate and Sparks, Athena},
  title = {Sandwiches for promise constraint satisfaction},
  journal = {Algebra universalis},
  year = {2021},
  volume = {82},
  number = {1},
  doi = {10.1007/s00012-020-00702-5}
}
Kostenlos starten →