Algebra i logika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Algebra Logika:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Algebra Logika, 2006, Volume 45, Number 6, Pages 655–686 (Mi al164)  

This article is cited in 5 scientific papers (total in 5 papers)

The property of being polynomial for Mal'tsev constraint satisfaction problems

A. A. Bulatov

Ural State University

Abstract: A combinatorial constraint satisfaction problem aims at expressing in unified terms a wide spectrum of problems in various branches of mathematics, computer science, and AI. The generalized satisfiability problem is NP-complete, but many of its restricted versions can be solved in a polynomial time. It is known that the computational complexity of a restricted constraint satisfaction problem depends only on a set of polymorphisms of relations which are admitted to be used in the problem. For the case where a set of such relations is invariant under some Mal'tsev operation, we show that the corresponding constraint satisfaction problem can be solved in a polynomial time.

Full text: PDF file (334 kB)
References: PDF file   HTML file

English version:
Algebra and Logic, 2006, 45:6, 371–388

Bibliographic databases:

UDC: 512.579
Received: 27.01.2006

Citation: A. A. Bulatov, “The property of being polynomial for Mal'tsev constraint satisfaction problems”, Algebra Logika, 45:6 (2006), 655–686; Algebra and Logic, 45:6 (2006), 371–388

Citation in format AMSBIB
\Bibitem{Bul06}
\by A.~A.~Bulatov
\paper The property of being polynomial for Mal'tsev constraint satisfaction problems
\jour Algebra Logika
\yr 2006
\vol 45
\issue 6
\pages 655--686
\mathnet{http://mi.mathnet.ru/al164}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2321085}
\zmath{https://zbmath.org/?q=an:1164.08307}
\transl
\jour Algebra and Logic
\yr 2006
\vol 45
\issue 6
\pages 371--388
\crossref{https://doi.org/10.1007/s10469-006-0035-2}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33845654821}


Linking options:
  • http://mi.mathnet.ru/eng/al164
  • http://mi.mathnet.ru/eng/al/v45/i6/p655

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. N. Lata, “Slabo regulyarnye unary so standartnoi maltsevskoi operatsiei”, Chebyshevskii sb., 14:4 (2013), 146–153  mathnet
    2. Barto L., Kozik M., “Constraint Satisfaction Problems Solvable By Local Consistency Methods”, J. ACM, 61:1 (2014), 3  crossref  mathscinet  isi  scopus
    3. V. L. Usoltsev, “O gamiltonovom zamykanii na klasse algebr s odnim operatorom”, Chebyshevskii sb., 16:4 (2015), 284–302  mathnet  elib
    4. S. N. Selezneva, “On weak positive predicates over a finite set”, Discrete Math. Appl., 30:3 (2020), 203–213  mathnet  crossref  crossref  mathscinet  isi  elib
    5. S. N. Selezneva, “On $m$-junctive predicates on a finite set”, J. Appl. Industr. Math., 13:3 (2019), 528–535  mathnet  crossref  crossref
  • Алгебра и логика Algebra and Logic
    Number of views:
    This page:355
    Full text:130
    References:35
    First page:6

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021