Том 26, номер 3, 2019 г., Стр. 46-59

УДК 519.7
Селезнева С. Н.
Об $m$-юнктивных предикатах на конечном множестве

Аннотация:
Рассматриваются предикаты на конечных множествах. Предикаты, инвариантные относительно некоторой ($m + 1$)-местной функции почти единогласия, названы $m$-юнктивными. Предлагается представление предикатов на конечном множестве в виде обобщённых конъюнктивных нормальных форм (ОКНФ). Получены свойства ОКНФ для $m$-юнктивных предикатов. Показано, что каждый $m$-юнктивный предикат может быть представлен полностью согласованной ОКНФ, в которой каждый конъюнкт содержит не более $m$ переменных. Такое представление $m$-юнктивного предиката названо приведённым. Предложен быстрый алгоритм нахождения приведённого представления $m$-юнктивного предиката. Показано, как полученные свойства ОКНФ для $m$-юнктивных предикатов можно применить для построения быстрого алгоритма задачи обобщённой $S$-выполнимости, в которой множество $S$ содержит только предикаты, инвариантные относительно одной и той же функции почти единогласия.
Библиогр. 15.

Ключевые слова: предикат на конечном множестве, функция на конечном множестве, функция почти единогласия, биюнктивный предикат, $m$-юнктивный предикат, конъюнктивная нормальная форма, задача обобщённой выполнимости.

DOI: 10.33048/daio.2019.26.647

Селезнева Светлана Николаевна ¹
1. Московский гос. университет им. М. В. Ломоноcова,
Ленинские горы, 1, 119991 Москва, Россия
е-mail: selezn@cs.msu.ru

Статья поступила 5 февраля 2019 г.
После доработки — 21 марта 2019 г.
Принята к публикации 25 марта 2019 г.

Литература

[1] Jeavons P., Coher D., Gyssens M. Closure properties of constraints // J. ACM. 1997. Vol. 44. P. 527–548.

[2] Bulatov A., Jeavons P., Krokhin A. Classifying the complexity of constraints using finite algebras // SIAM J. Comput. 2005. Vol. 34, No. 3. P. 720–742.

[3] Zhuk D. An algorithm for constraint satisfaction problem // Proc. IEEE 47th Int. Symp. Multiple-Valued Logic. 2017. P. 1–6.

[4] Zhuk D. A proof of CSP dichotomy conjecture // Proc. IEEE 58th Annu. Symp. Foundations of Computer Science (Berkeley, CA). 2017. P. 331–342

[5] Bulatov A. A. A dichotomy theorem for nonuniform CSPs // Proc. IEEE 58th Annu. Symp. Foundations of Computer Science (Berkeley, CA). 2017. P. 319–330

[6] Schaefer T. Complexity of satisfiability problems // Proc. 10th ACM Symp. Theory of Computing. 1978. P. 216–226.

[7] Bulatov A. A. A dichotomy theorem for constraint satisfaction problems on a 3-element set // J. ACM. 2006. Vol. 53, No. 1. P. 66–120.

[8] Jeavons P., Cohen D., Cooper M. Constraints, consistency and closure // Artif. Intell. 1998. Vol. 101, No. 1–2. P. 251–265.

[9] Jeavons P. J., Cooper M. C. Tractable constraints on ordered domains // Artif. Intell. 1995. Vol. 79. P. 327–339.

[10] Булатов А. А. Полиномиальность мальцевских задач CSP // Алгебра и логика. 2006. Т. 45, № 6. С. 655–686.

[11] Селезнева С. Н. О биюнктивных предикатах над конечным множеством // Дискрет. математика. 2017. Т. 29, вып. 4. С. 130–142.

[12] Селезнева С. Н. О слабо положительных предикатах над конечным множеством // Дискрет. математика. 2018. Т. 30, вып. 3. С. 127–140.

[13] Dechter R. From local to global consistency // Artif. Intell. 1992. Vol. 55. P. 87–107.

[14] Cooper M. C. An optimal $k$-consistency algorithm // Artif. Intell. 1989. Vol. 41. P. 89–95.

[15] Lau D. Function algebras on finite sets. Springer, 2006.