Page 137 - 4495

 0 0 1  1 0 1  0 1 0    0 0 1

           a  [b c ] a
 0 1 1    0 0 0   0 0 1   0 1 1 
Отже, приходимо до висновку, що у даній ієрархії і будь – якому
c - напівкільцю з компаратором типу «регіонально краще» не може

існувати адитивної операції що є асоціативною. А оскільки асоціати-
вність адитивної операції є однією з головних властивостей напівкі-
льцевої CSP, то класу напівкільцевої CSP для ІО з компаратором «ре-
гіонально краще» існувати не може.

Категоризація ієрархій зі скінченними доменами
Було задано класи напівкільцевої CSP для компараторів «лекси-
кографічно краще», «краще за сумарною вагою», та компараторів

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

поліноміального перетворення. ІО з локальними компараторами на-
лежать до окремого класу задач, оскільки в них напівкільцеві множи-
ни є частково впорядкованими. Локальна напівкільцева CSP може бу-

ти перетворена в вагову CSP, якщо застосувати поліноміальне част-
кове удосконалення. Однак, зворотнє перетворення неможливе через
часткове впорядкування у множині присвоєнь ІО. Всі зв’язки між

класами напівкільцевої CSP, а також їх властивості, показані на рис 3.
Вагова та лексикографічна напівкільцеві CSP можуть бути задані
як класи оцінної CSP при використанні прямого розв'язку між напів-

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

параторів.
Вагова напівкільцева CSP
Вагова напівкільцева CSP є нічим іншим, як першим необ-

ов’язковим рівеннм ієрархії обмежених з компаратором «краще за
сумарною вагою». Існує просте поліноміальне часове удосконалення,
яке перетворює ІО з компаратором «краще за сумарною вагою» у
просту вагову CSP.

137