Частичный циклический порядок
В математике частичный циклический порядок — это троичное отношение , которое обобщает циклический порядок так же, как частичный порядок обобщает линейный порядок .
Над заданным набором частичный циклический порядок представляет собой троичное отношение , которое:
Отношения между частичными и полными циклическими заказами более сложны, чем отношения между частичными и полными линейными заказами. Начнем с того, что не каждый частичный циклический порядок может быть расширен до полного циклического порядка. Примером может служить следующее отношение для первых тринадцати букв алфавита: { acd, bde, cef, dfg, egh, fha, gac, hcb } ∪ { abi, cij, bjk, ikl, jlm, kma, lab, mbc } . Это отношение является частичным циклическим порядком, но его нельзя расширить ни с помощью abc , ни сba ; любая попытка приведет к противоречию. [4]
Выше был относительно мягкий пример. Можно также построить частичные циклические порядки с препятствиями более высокого порядка, так что, например, можно добавить любые 15 троек, но нельзя добавить 16-ю. На самом деле циклическое упорядочение является NP-полным , так как оно решает 3SAT . Это резко контрастирует с проблемой распознавания линейных порядков, которую можно решить за линейное время . [5] [6]