СС (сложность)

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

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

Важнейшей задачей, решаемой для КЦ, является вариант решения проблемы устойчивого брака .

Определение

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

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

Проблема значения схемы компаратора (CCVP) — это проблема оценки схемы компаратора с учетом кодирования схемы и входных данных схемы. Класс сложности CC определяется как класс лог-пространства задач , сводимый к CCVP. Эквивалентное определение — класс задач AC ⁰ сводится к CCVP.

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

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

CC-полные проблемы

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

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

Другая проблема, которая является CC -полной, - это лексикографически первое максимальное паросочетание. В этой задаче нам дан двудольный граф с порядком вершин и ребром. Первое с лексикографической точки зрения максимальное сопоставление получается путем последовательного сопоставления вершин из первого бираздела с минимальными доступными вершинами из второго бираздела. Задача состоит в том, принадлежит ли данное ребро этому паросочетанию.

Скотт Ааронсон показал, что модель гальки является CC -полной. В этой задаче нам дано стартовое количество камешков (закодированное в унарном коде ) и описание программы, которая может содержать только два типа инструкций: соединить две кучки разных размеров. $y$ и $z$ чтобы получить новую кучу размера $y+z$, или разделить стопку размером $y$ в кучки по размеру $\lceil y/2\rceil$ и $\lfloor y/2\rfloor$. Проблема состоит в том, чтобы после выполнения программы решить, присутствуют ли камешки в конкретной куче. Он использовал это, чтобы показать, что проблема определения того, достигают ли какие-либо шары назначенной вершины стока в устройстве, подобном Digi-Comp II, также является CC -полной.

Условия содержания

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

Внешние ссылки

• Зоопарк сложности : CC