Page 115 - 4495

Як наслідок з виводу 2 отримуємо твердження про те, що якщо
щось є непорівнюваним в одній з еквівалентних задач, воно мусить
бути непорівнюваним також і в усіх інших задачах, еквівалентних
початковій.

Щоб мати змогу порівняти класи напівкільцевої CSP, які буду-
ються на різних напівкільцевих структурах, введемо поняття поліно-
міального удосконалення.

Означення 43 (поліноміальне часове удосконалення). Нехай
задано два c– напівкільця - S та S. Поліноміальним частковим удо-
сконаленням із S в Sназивається функція  , така, що трансформує


будь-яку напівкільцеву CSP P  (C ,con ), у якій визначена множина об-
межень C   i (def con на системі обмежень (S , D ,con i ), у напівільцеву

)
i
, i
CSP P  (C ,con ), де C  i  (def con на множині (S , D ,con ). Рівність
)
, i
i
def   de f  справедливе для всіх iтаких, що P - удосконалення P;
i i
Якщо існує поліноміальне часове удосконалення із S в S , то
будь-яка напівкільцева CSP P над S може бути розв’язана шляхом
застосування цього вдосконалення до P і потім розв’язанням резуль-
туючої задачі над S , тобто задачі, визначені над S, не є складнішими
від задач, визначених над S .
Класи напівкільцевої CSP

Конкретні класи напівкільцевої одержуютья шляхом задання
структури на півкільце. Ці задання узагальнені в таблиці 2.
Дивлячись на таблицю, легко можна побачити відповідність між

напівкільцевою та оцінною CSP. Також детальний опис окремих кла-
сів аналогічний як для напівкільцевої, так і для оціночної CSP. Для
порівняння з класами оцінної CSP, опишемо нечітку CSP, а також ін-
шу модель, т. зв. лексикографічну CSP.

Нечітка CSP
Про нечітку CSP як клас напівкільцевої можна судити з огляду на
пряму відповідність як комбінаційної, так і проекційної операції. На-

півкільцева множина задається інтервалом 0 , в якому «найкращий»
1 ,
елемент дорівнює одиниці, а «найгірший» - нулю. В результаті маємо
на півкільце ( , 1 , 0 max, min, ) 1 , 0 для кон’юктивної операції. При розгляді

продуктивної комбінації, операція min замінюється на . Однак, сере-
дньоарифметична операція не може розглядатися в напівкільцевій
CSP, оскільки вона не є асоціативною, що є обов’язковою вимогою

напівкільцевої структури.

Таблиця 2 – Узагальнена специфікація A , , ,0,1 

115