Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец

Abstract

Предложено обобщение известной задачи удовлетворения ограничений в терминах операций коммукативного полукольца. Показано, что известный полиномиально разрешимый подкласс задач с мажоритарным полиморфизмом разрешим и для обобщенной задачи.

Запропоновано узагальнення відомої задачі задовільнення обмежень в термінах операцій комукативного напівкільця. Показано, що відомий поліноміально розв’язний підклас задач з мажоритарним поліморфізмом є розв’язним і для узагальненої задачі.

The article generalizes the known constraint satisfaction problems in terms of a commutative semiring. It is shown that a known track table subclass with a majority polymorphism is also track table in the generalized problem. The constraint satisfaction problems can be defined as computing the disjunction over the set of all variable values of all constraints conjunction. This definition can be generalized to computing the sum of products in a commutative semi ring. One of the track table subclasses of the classical constraint satisfaction problems semering are problems with a majority polymorphism. The article generalizes the definition of polymorphisms to commutative semi rings with the idempotent sum and product and defines a track table subclass for the generalized problem. Many of the useful properties of the classical polymorphisms proved to be true with the generalized polymorphism definition. It is shown that any generalized constraint satisfaction problem with a majority polymorphism can be solved in polynomial time. An algorithm that solves the problem is given and is based on the equivalent star to simplex transformations of the problem by excluding variables one at a time.