Схемы над множествами натуральных чисел

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

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

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

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

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

Алгоритмические задачи

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

Является ли данное число n членом выходного узла.
Выходной узел пуст?
Является ли один узел подмножеством другого.

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

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

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

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

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

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

Ограничения

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

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

Одна из трудностей связана с тем, что дополнение конечного множества бесконечно, а у компьютера есть только конечная память. Но даже без дополнения можно получить двойные показательные числа. Позволять $E_{0}=\{2\},E_{i+1}=E_{i}\times E_{i}$ , то легко доказать индукцией по $i$ что $E_{i}=\{2^{2^{i}}\}$ , действительно $E_{0}=\{2\}=\{2^{1}\}=\{2^{2^{0}}\}$ и по индукции $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}}\}$ .

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

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

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

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

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

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

Сложность
ТО	МС(О)	МФ(О)
∪,∩,−,+,×	СЛЕДУЮЩИЙ ВРЕМЯ - жесткий Решается с помощью оракула для проблемы остановки	PSPACE -жесткий
∪,∩,+,×	СЛЕДУЮЩЕЕ ВРЕМЯ - завершено	NP-полный
∪,+,×	PSPACE -полный	NP-полный
∩,+,×	П -жесткий, в со- РП	в D LOGCFL
+,×	П -полный	в D LOGCFL
∪,∩,−,+	PSPACE -полный	PSPACE -полный
∪,∩,+	PSPACE -полный	NP-полный
∪,+	NP-полный	NP-полный
∩,+	C ₌ L -полный	в Л
+	C ₌ L -полный	в Л
∪,∩,−,×	PSPACE -полный	PSPACE -полный
∪,∩,×	PSPACE -полный	NP-полный
∪,×	NP-полный	NP-полный
∩,×	C ₌ L -жесткий, в P	в Л
×	НЛ -полный	в Л
∪,∩,−	П -полный	Северная Каролина ¹-полный
∪,∩	П -полный	в Северной Каролине ¹
∪	НЛ -полный	в Северной Каролине ¹
∩	НЛ -полный	в Северной Каролине ¹

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

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

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

Сложность
ТО	ЭК(О)	ЭФ(О)
∪,∩,−,+,×	СЛЕДУЮЩИЙ ВРЕМЯ - жесткий Решается с помощью оракула для проблемы остановки	PSPACE -жесткий Решается с помощью оракула для проблемы остановки
∪,∩,+,×	NEXPTIME -жесткий, в сочетании с NEXP ^{НАПРИМЕР}	П ^П₂ -полный
∪,+,×	NEXPTIME -жесткий, в сочетании с NEXP ^{НАПРИМЕР}	П ^П₂ -полный
∩,+,×	P -жесткий, в БПП	P -жесткий, в БПП
+,×	P -жесткий, в БПП	П -хард, в ко РП
∪,∩,−,+	PSPACE -полный	PSPACE -полный
∪,∩,+	PSPACE -полный	П ^П₂ -полный
∪,+	П ^П₂ -полный	П ^П₂ -полный
∩,+	co C ₌ L (2)-полный	в Л
+	C ₌ L -полный	в Л
∪,∩,−,×	PSPACE -полный	PSPACE -полный
∪,∩,×	PSPACE -полный	П ^П₂ -полный
∪,×	П ^П₂ -полный	П ^П₂ -полный
∩,×	co C ₌ L (2)-жесткий, в P	в Л
×	C ₌ L -жесткий, в P	в Л
∪,∩,−	П -полный	Северная Каролина ¹-полный
∪,∩	П -полный	Северная Каролина ¹-полный
∪	НЛ -полный	в Северной Каролине ¹
∩	НЛ -полный	в Северной Каролине ¹

Ссылки

^ Кристиан Глассер; Катрин Херр; Кристиан Райтвиснер; Стивен Трэверс; Маттиас Вальдхерр (2007), Информатика – теория и приложения , Конспекты лекций по информатике, том. 4649/2007 ((то, что в bibtex называется «номером») изд.), Берлин / Гейдельберг: Springer, стр. 127–138, doi : 10.1007/978-3-540-74510-5 , ISBN 978-3-540-74509-9

Трэверс, Стивен (2006), «Сложность проблем принадлежности для схем над наборами натуральных чисел», Theoretical Computer Science , 389 (1): 211–229, doi : 10.1016/j.tcs.2006.08.017 , ISSN 0304- 3975

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

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

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

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

[1] Кристиан Глассер; Катрин Херр; Кристиан Райтвиснер; Стивен Трэверс; Маттиас Вальдхерр (2007), Информатика – теория и приложения , Конспекты лекций по информатике, том. 4649/2007 ((то, что в bibtex называется «номером») изд.), Берлин / Гейдельберг: Springer, стр. 127–138, doi : 10.1007/978-3-540-74510-5 , ISBN 978-3-540-74509-9

[1]