CC (сложность)
-
Определение и функции схем сравнения
- CC — это класс задач, решаемых с помощью схем сравнения, которые могут быть полиномиального размера.
- Схемы компаратора представляют собой сети, в которых каждый элемент управляет двумя проводами и выводит их в упорядоченном виде.
- Входные данные могут быть переменными, их отрицаниями или константами, а один из проводов является выходным.
-
Проблема определения значения схемы сравнения
- CCVP — это проблема оценки схемы сравнения, учитывая кодировку и входные данные.
- CC определяется как класс задач, которые могут быть сведены к CCVP.
-
Примеры задач в CC
- Вычисление большинства с помощью сортировочной сети, где средний провод является выходным.
- Проблема стабильного брака, где требуется определить, есть ли стабильные пары без непарных предпочтений.
- Лексикографически первое максимальное соответствие, где требуется определить, принадлежит ли ребро к определенному соответствию.
-
CC-полные задачи
- Проблема стабильного брака и лексикографически первое максимальное соответствие являются CC-полными задачами.
- Проблема определения, достигают ли шары заданной вершины в устройстве, подобном Digi-Comp II, также является CC-полной.
-
Сдерживающие факторы и рекомендации
- Оценка схемы компаратора может быть выполнена за полиномиальное время, что указывает на ее принадлежность к классу P.
- Схемы сравнения могут решать задачу направленной достижимости, что указывает на их принадлежность к классу NL.
- Существуют релятивизированные миры, где CC и NC несравнимы, что подчеркивает строгость этих классов сложности.
Полный текст статьи: