|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Strong Subalgebras and the Constraint Satisfaction Problemстатья
Статья опубликована в высокорейтинговом журнале
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 4 августа 2021 г.
- Автор: ZHUK D.
- Журнал: Journal of Multiple-Valued Logic and Soft Computing
- Том: 36
- Номер: 4/5
- Год издания: 2021
- Издательство: Old City Publishing, Inc.
- Местоположение издательства: United States
- Первая страница: 455
- Последняя страница: 504
- Аннотация: In 2007 it was conjectured that the Constraint Satisfaction Problem (CSP) over a constraint language Γ is tractable if and only if Γ is preserved by a weak near-unanimity (WNU) operation. After many efforts and partial results, this conjecture was independently proved by Andrei Bulatov and the author in 2017. In this paper we consider one of two main ingredients of my proof, that is, strong subalgebras that allow us to reduce domains of the variables iteratively. To explain how this idea works we show the algebraic properties of strong subalgebras and provide self-contained proof of two important facts about the complexity of the CSP. First, we prove that if a constraint language is not preserved by a WNU operation then the corresponding CSP is NP-hard. Second, we characterize all constraint languages that can be solved by local consistency checking. Additionally, we characterize all idempotent algebras not having a WNU term of a concrete arity n, not having a WNU term, having WNU terms of all arities greater than 2. Most of the results presented in the paper are not new, but I believe this paper can help to understand my approach to CSP and the new self-contained proof of known facts will be also useful.
- Добавил в систему: Жук Дмитрий Николаевич