CC (сложность) - CC (complexity)

В теория сложности вычислений, CC (схемы компаратора) это класс сложности содержащий проблемы решения что может быть решено схемами компаратора многочлен размер.

Схемы компаратора сортировочные сети в котором каждый вентиль компаратора направлен, каждый провод инициализируется входной переменной, ее отрицанием или константой, и один из проводов выделяется как выходной провод.

Самая главная задача, которая решена за CC это вариант решения проблема стабильного брака.

Определение

Компараторный вентиль.
Один вентиль компаратора.

Схема компаратора - это сеть проводов и вентилей. Каждый вентиль компаратора, который представляет собой направленное ребро, соединяющее два провода, принимает два своих входа и выводит их в отсортированном порядке (большее значение попадает в провод, на который указывает ребро). Вход в любой провод может быть либо переменной, либо ее отрицанием, либо константой. Один из проводов обозначен как выходной провод. Функция, вычисляемая схемой, оценивается путем инициализации проводов в соответствии с входными переменными, выполнения вентилей компаратора по порядку и вывода значения, переносимого выходным проводом.

Проблема значения схемы компаратора (CCVP) - это проблема оценки схемы компаратора с учетом кодирования схемы и входа в схему. Класс сложности CC определяется как класс проблем пространство журнала сводится к CCVP.[1] Эквивалентное определение[2] это класс проблем AC0 сводится к CCVP.

Например, для вычисления большинства можно использовать сеть сортировки, обозначив средний провод как выходной провод:

Сеть сортировки, которую можно использовать для вычисления большинства.

Если средний провод обозначен как выход, а провода помечены 16 различными входными переменными, то результирующая схема компаратора вычисляет большинство. Поскольку существуют сортировочные сети, которые можно построить в AC0, это показывает, что мажоритарная функция находится в CC.

CC-Complete задачи

Проблема в CC является CC-полно, если все проблемы в CC можно свести к нему с помощью пространство журнала снижение. Проблема значения схемы компаратора (CCVP): CC-полный.

в проблема стабильного брака, есть равное количество мужчин и женщин. Каждый оценивает всех представителей противоположного пола. Соответствие между мужчиной и женщиной - это стабильный если нет непарных мужчины и женщины, которые предпочитают друг друга своим нынешним партнерам. Всегда существует стабильное соответствие. Среди стабильных совпадений есть такое, в котором каждая женщина получает лучшего мужчину, которого она когда-либо встречала в любом стабильном совпадении; это известно как женщина-оптимальный стабильное соответствие. Вариант решения задачи стабильного сопоставления состоит в том, учитывая ранжирование всех мужчин и женщин, сопоставимы ли данный мужчина и данная женщина в оптимальном для женщин стабильном сопоставлении. Хотя классический алгоритм Гейла – Шепли не может быть реализован в виде схемы компаратора, Субраманиан[3] придумал другой алгоритм, показывающий, что проблема в CC. Проблема также в CC-полный.

Еще одна проблема, которая CC-полное - это лексикографически первое максимальное соответствие.[3] В этой задаче нам дан двудольный граф с порядком в вершинах и ребром. Лексикографически первое максимальное сопоставление получается путем последовательного сопоставления вершин из первого двудольного деления с минимально доступными вершинами из второго двудольного деления. Проблема спрашивает, принадлежит ли данное ребро этому совпадению.

Скотт Ааронсон показал, что модель гальки является CC-полный.[4] В этой задаче нам дается начальное количество камешков (закодировано в унарный ) и описание программы, которая может содержать только два типа инструкций: объединить две стопки размеров и получить новую стопку размера , или разделите стопку по размеру в стопки по размеру и . Проблема состоит в том, чтобы определить, присутствуют ли какие-либо камешки в конкретной куче после выполнения программы. Он использовал это, чтобы показать, что проблема определения того, достигают ли какие-либо шары обозначенной вершины стока в Digi-Comp II -подобное устройство также CC-полный.

Контейнеры

Задача оценки схемы компаратора может быть решена за полиномиальное время, и поэтому CC содержится в п («универсальность схемы»). С другой стороны, схемы компаратора могут решить направленную достижимость,[3] и так CC содержит NL. Есть релятивизированный мир, в котором CC и NC несравненные,[2] и поэтому обе меры сдерживания строги.

Рекомендации

  1. ^ Э. В. Майр; А. Субраманян (1992). «Сложность схемотехники и стабильность сети». Журнал компьютерных и системных наук. 44 (2): 302–323. Дои:10.1016 / 0022-0000 (92) 90024-д.
  2. ^ а б С. А. Кук; Ю. Фильмус; Д. Т. М. Ле (2012). «Сложность проблемы стоимости схемы компаратора». arXiv:1208.2721.
  3. ^ а б c А. Субраманян (1994). «Новый подход к задачам стабильного согласования». SIAM Журнал по вычислениям. 23 (4): 671–700. Дои:10.1137 / s0097539789169483.
  4. ^ Ааронсон, Скотт (4 июля 2014 г.). "Сила Digi-Comp II". Штетл-Оптимизированный. Получено 28 июля 2014.

внешняя ссылка