СС (сложность)
В теории сложности вычислений CC (схемы сравнения) — это класс сложности содержащий проблемы решения , которые могут быть решены с помощью схем сравнения полиномиального , размера.
Схемы компаратора представляют собой сортировочные сети , в которых каждый вентиль компаратора направлен, каждый провод инициализируется входной переменной, ее отрицанием или константой, а один из проводов выделяется как выходной провод.
Важнейшей задачей, решаемой для КЦ, является вариант решения проблемы устойчивого брака .
Определение [ править ]
Схема компаратора представляет собой сеть проводов и вентилей. Каждый вентиль компаратора, который представляет собой направленное ребро, соединяющее два провода, принимает два своих входа и выводит их в отсортированном порядке (большее значение попадает в провод, на который указывает край). Входным сигналом для любого провода может быть переменная, ее отрицание или константа. Один из проводов обозначен как выходной. Функция, вычисленная схемой, оценивается путем инициализации проводов в соответствии с входными переменными, последовательного выполнения логических элементов компаратора и вывода значения, передаваемого выходным проводом.
Проблема значения схемы компаратора (CCVP) — это проблема оценки схемы компаратора с учетом кодирования схемы и входных данных схемы. Класс сложности CC определяется как класс лог-пространства задач , сводимый к CCVP. [1] Эквивалентное определение [2] — класс задач AC 0 сводится к CCVP.
Например, для вычисления большинства можно использовать сортировочную сеть, назначив средний провод выходным проводом:
Если средний провод обозначен как выходной, а провода помечены 16 различными входными переменными, то результирующая схема компаратора вычисляет большинство. Поскольку существуют сортировочные сети, которые можно построить в АС 0 , это показывает, что основная функция большинства находится в CC .
CC-полные проблемы [ править ]
Задача в CC является CC -полной, если каждую задачу в CC можно свести к ней с помощью сокращения пространства журнала . Задача о значении схемы компаратора (CCVP) является CC -полной.
В проблеме стабильного брака количество мужчин и женщин равное. Каждый человек ранжирует всех представителей противоположного пола. Соответствие между мужчиной и женщиной стабильно , если нет непарных мужчины и женщины, которые предпочитают друг друга своим нынешним партнерам. Устойчивое паросочетание всегда существует. Среди стабильных спариваний есть один, в котором каждая женщина получает лучшего мужчину, которого она когда-либо получала в любом стабильном спаривании; это известно как оптимальное для женщины стабильное соответствие. Вариант решения проблемы стабильного соответствия заключается в том, что, учитывая рейтинг всех мужчин и женщин, сопоставляются ли данный мужчина и данная женщина в оптимальном для женщины стабильном сопоставлении. Хотя классический алгоритм Гейла – Шепли не может быть реализован как схема компаратора, Субраманиан [3] придумал другой алгоритм, показывающий, что проблема в CC . Проблема также CC -полна.
Другая проблема, которая является CC -полной, - это лексикографически первое максимальное паросочетание. [3] В этой задаче нам дан двудольный граф с порядком вершин и ребром. Лексикографически первое максимальное сопоставление получается путем последовательного сопоставления вершин из первого бираздела с минимально доступными вершинами из второго бираздела. Задача состоит в том, принадлежит ли данное ребро этому паросочетанию.
Скотт Ааронсон показал, что модель гальки является CC -полной. [4] В этой задаче нам дано стартовое количество камешков (закодированное в унарном коде ) и описание программы, которая может содержать только два типа инструкций: соединить две кучки разных размеров. и чтобы получить новую кучу размера , или разделить стопку размером в кучки по размеру и . Проблема состоит в том, чтобы после выполнения программы решить, присутствуют ли камешки в конкретной куче. Он использовал это, чтобы показать, что проблема определения того, достигают ли какие-либо шарики назначенной вершины стока в устройстве, подобном Digi-Comp II, также является CC -полной.
Условия содержания [ править ]
Задача оценки схемы компаратора может быть решена за полиномиальное время, поэтому CC содержится в P («универсальность схемы»). С другой стороны, схемы компаратора могут решить проблему направленной достижимости. [3] и поэтому CC содержит NL . Существует релятивизированный мир, в котором CC и NC несравнимы, [2] и поэтому оба сдерживания являются строгими.
Ссылки [ править ]
- ^ Э.В. Майр; А. Субраманян (1992). «Сложность схемы и стабильность сети» . Журнал компьютерных и системных наук . 44 (2): 302–323. дои : 10.1016/0022-0000(92)90024-д .
- ^ Перейти обратно: а б С.А. Кук; Ю. Фильмус; ДТМ Ле (2012). «Сложность проблемы значения схемы компаратора». arXiv : 1208.2721 .
- ^ Перейти обратно: а б с А. Субраманян (1994). «Новый подход к решению задач стабильного сопоставления». SIAM Journal по вычислительной технике . 23 (4): 671–700. дои : 10.1137/s0097539789169483 .
- ^ Ааронсон, Скотт (4 июля 2014 г.). «Сила Digi-Comp II» . Shtetl-Оптимизированный . Проверено 28 июля 2014 г.