Цепи над наборами натуральных чисел - Circuits over sets of natural numbers

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

Как алгоритмический Проблема состоит в том, чтобы определить, является ли данное натуральное число элементом выходного узла или две схемы вычисляют один и тот же набор. Разрешимость остается открытым вопросом.

Формальное определение

Схема натуральных чисел - это схема, т. е. помеченный ориентированный ациклический граф внутренней степени не выше 2. Узлы внутренней степени 0, листы, представляют собой конечные наборы натуральных чисел, метки узлов внутренней степени 1 -, где ${ displaystyle { overline {A}} = {x in mathbb {N} | x not in A }}$ а метки узлов степени 2 равны +, ×, ∪ и ∩, где ${ Displaystyle A + B = {a + b | a in A, b in B }}$, ${ displaystyle A times B = {a times b | a in A, b in B }}$ и ∪ и ∩ с обычными набор смысл.

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

Алгоритмические проблемы

Можно спросить:

• Данное число п член выходного узла.
• Выходной узел пуст?
• Является ли один узел частью другого.

Для схем, использующих все метки, все эти проблемы эквивалентны.

Доказательство

Первая проблема сводится ко второй, взяв пересечение выходного элемента и п. Действительно, новый вывод get будет пустым тогда и только тогда, когда п не был элементом бывшего выходного затвора.

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

Вторая проблема сводится к первой, достаточно умножить выходной вентиль на 0, тогда 0 будет в выходном вентиле тогда и только тогда, когда предыдущий выходной вентиль не был пуст.

Третья проблема сводится ко второй, проверка того, является ли A подмножеством B, эквивалентна вопросу о том, есть ли элемент в ${ displaystyle A cap { overline {B}}}$.

Ограничения

Пусть O - подмножество {∪, ∩, -, +, ×}, тогда мы называем MC (O) задачей определения того, находится ли натуральное число внутри выходного элемента схемы, метки элементов которой находятся в O , и MF (O) та же проблема с добавленным ограничением, что схема должна быть дерево.

Быстрорастущий набор

Одна трудность возникает из-за того, что дополнение к конечному множеству бесконечно, а компьютер имеет только конечную память. Но даже без дополнений можно создать двойная экспонента числа. Позволять ${ displaystyle E_ {0} = {2 }, E_ {i + 1} = E_ {i} times E_ {i}}$, то легко доказать индукцией по ${ displaystyle i}$ который ${ displaystyle E_ {i} = {2 ^ {2 ^ {i}} }}$, в самом деле ${ Displaystyle E_ {0} = {2 } = {2 ^ {1} } = {2 ^ {2 ^ {0}} }}$ и по индукции ${ displaystyle E_ {i + 1} = E_ {i} times E_ {i} = {2 ^ {2 ^ {i}} } times {2 ^ {2 ^ {i}} } = {(2 ^ {2 ^ {i}}) ^ {2} } = {2 ^ {2 ^ {i} times 2} } = {2 ^ {2 ^ {i + 1}} }}$.

И даже наборы двойного экспоненциального размера: пусть ${ Displaystyle S_ {0} = {0,1,2 }, S_ {i + 1} = (S_ {i} times S_ {i}) + S_ {i}}$, тогда ${ Displaystyle {х | 0 <х <2 ^ {2 ^ {я}} } подмножество S_ {я}}$, т.е. ${ displaystyle S_ {i}}$ содержит ${ displaystyle 2 ^ {2 ^ {i}}}$ первый номер. Еще раз это можно доказать индукцией по ${ displaystyle i}$, это верно для ${ displaystyle S_ {0}}$ по определению и пусть ${ Displaystyle х в {х | 0 <х <2 ^ {2 ^ {я + 1}} }}$, деля ${ displaystyle x}$ к ${ displaystyle 2 ^ {2 ^ {i}}}$ мы видим, что это можно записать как ${ displaystyle x = 2 ^ {2 ^ {i}} times d + r}$ куда ${ displaystyle d, r <2 ^ {2 ^ {i}}}$, а по индукции ${ displaystyle 2 ^ {2 ^ {i}}, d}$ и ${ displaystyle r}$ находятся в ${ displaystyle S_ {i}}$так что действительно ${ displaystyle x in (S_ {i} times S_ {i}) + S_ {i}}$.

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

Результаты сложности

Проблема членства

Проблема членства спрашивает, если, учитывая элемент п и цепь, п находится в выходном затворе схемы.

Когда класс авторизованных шлюзов ограничен, проблема членства лежит внутри хорошо известных классов сложности. Обратите внимание, что переменная размера здесь - это размер схемы или дерева; значение п считается фиксированным.

Сложность

О	MC (O)	MF (O)
∪,∩,−,+,×	NEXPTIME -жесткий Разрешается с помощью оракул для проблема остановки	PSPACE -жесткий
∪,∩,+,×	NEXPTIME -полный	НП-полный
∪,+,×	PSPACE -полный	НП-полный
∩,+,×	п -жесткий, в со-RP	в DLOGCFL
+,×	п -полный	в DLOGCFL
∪,∩,−,+	PSPACE -полный	PSPACE -полный
∪,∩,+	PSPACE -полный	НП-полный
∪,+	НП-полный	НП-полный
∩,+	C=L -полный	в L
+	C=L -полный	в L
∪,∩,−,×	PSPACE -полный	PSPACE -полный
∪,∩,×	PSPACE -полный	НП-полный
∪,×	НП-полный	НП-полный
∩,×	C=L твердый, в п	в L
×	NL -полный	в L
∪,∩,−	п -полный	NC1 -полный
∪,∩	п -полный	в NC1
∪	NL -полный	в NC1
∩	NL -полный	в NC1

Проблема эквивалентности

Проблема эквивалентности спрашивает, дают ли два логических элемента схемы одно и то же множество.

Когда класс авторизованных шлюзов ограничен, проблема эквивалентности лежит внутри хорошо известных классов сложности.^[1] Мы называем EC (O) и EF (O) проблемой эквивалентности над схемами и формулами, элементы которых находятся в O.

Сложность

О	EC (O)	EF (O)
∪,∩,−,+,×	NEXPTIME -жесткий Разрешается с помощью оракул для проблема остановки	PSPACE -жесткий Разрешается с помощью оракул для проблема остановки
∪,∩,+,×	NEXPTIME жесткий, в соNEXPНП	Πп2 -полный
∪,+,×	NEXPTIME жесткий, в соNEXPНП	Πп2 -полный
∩,+,×	п твердый, в BPP	п твердый, в BPP
+,×	п твердый, в BPP	п -жесткий, в соRP
∪,∩,−,+	PSPACE -полный	PSPACE -полный
∪,∩,+	PSPACE -полный	Πп2 -полный
∪,+	Πп2 -полный	Πп2 -полный
∩,+	coC=L (2) -полный	в L
+	C=L -полный	в L
∪,∩,−,×	PSPACE -полный	PSPACE -полный
∪,∩,×	PSPACE -полный	Πп2 -полный
∪,×	Πп2 -полный	Πп2 -полный
∩,×	coC=L (2) -твердый, в п	в L
×	C=L твердый, в п	в L
∪,∩,−	п -полный	NC1 -полный
∪,∩	п -полный	NC1 -полный
∪	NL -полный	в NC1
∩	NL -полный	в NC1

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

• Трэверс, Стивен (2006), «Сложность задач о принадлежности схем над множествами натуральных чисел», Теоретическая информатика: журнал Европейской ассоциации теоретической информатики, Теоретическая информатика, 389 (1): 211–229, Дои:10.1016 / j.tcs.2006.08.017, ISSN  0304-3975

• Пьер Маккензи; Клаус В. Вагнер (2003), «Сложность задач о принадлежности схем над множествами натуральных чисел», Конспект лекций по информатике, Springer-Verlag, 2607: 571–582, Дои:10.1007/3-540-36494-3_50, ISBN  3-540-00623-0

• Бройниг, Ханс-Георг (2007), Сложность проблем принадлежности схем над множествами положительных чисел, FCT'07 Труды 16-й международной конференции по основам теории вычислений, Springer-Verlag, pp. 125–136, ISBN  978-3-540-74239-5

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

• Пьер Маккензи, Сложность вычисления схемы по натуральным числам