Это происходит повсюду

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

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

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

Сложность проблемы членства

Проблема принадлежности — это проблема принятия решения, учитывая целочисленную схему C , входные данные схемы X и конкретное целое число n , находится ли целое число n на выходе схемы C, ему предоставляется входной сигнал X. когда Вычислительная сложность этой задачи зависит от типа вентилей, разрешенных в C. схеме ^[1] В таблице ниже суммирована вычислительная сложность проблемы принадлежности для различных классов целочисленных схем.Вот, МФ $_{\mathbb {Z} }$ (O) обозначает классы, определяемые O-формулами, которые являются O-схемами с максимальным разветвлением 1.

Сложность
ТО	МК $_{\mathbb {Z} }$ (ТО)	МФ $_{\mathbb {Z} }$ (ТО)
∪,∩,−,+,×	СЛЕДУЮЩИЙ ВРЕМЯ - жесткий	PSPACE -жесткий
∪,∩,+,×	СЛЕДУЮЩЕЕ ВРЕМЯ - завершено	NP-полный
∪,+,×	СЛЕДУЮЩЕЕ ВРЕМЯ - завершено	NP-полный
∩,+,×	P -жесткий, в со-NP	L -жесткий, в LOGCFL
+,×	P -жесткий, в со-NP	L -жесткий, в LOGCFL
∪,∩,−,+	PSPACE -полный	PSPACE -полный
∪,∩,+	PSPACE -полный	NP-полный
∪,+	NP-полный	NP-полный
∩,+	C ₌ L -полный	L -полный
+	C ₌ L -полный	L -полный
∪,∩,−,×	PSPACE -полный	PSPACE -полный
∪,∩,×	PSPACE -полный	NP-полный
∪,×	NP-полный	NP-полный
∩,×	( С ₌ L $\land \oplus$ Л)-жесткий, в П	L -полный
×	( NL -полный $\land \oplus$ Л)-полный	L -полный
∪,∩,−	П -полный	L -полный
∪,∩	П -полный	L -полный
∪	НЛ -полный	L -полный
∩	НЛ -полный	L -полный

Ссылки

^ Стивен Трэверс (2006), «Сложность проблем принадлежности для схем над наборами целых чисел», Theoretical Computer Science , 369 (1) (1–3 изд.), Эссекс, Великобритания: Elsevier Science Publishers Ltd: 211–229, doi : 10.1016/j.tcs.2006.08.017 , ISSN 0304-3975

[1] Стивен Трэверс (2006), «Сложность проблем принадлежности для схем над наборами целых чисел», Theoretical Computer Science , 369 (1) (1–3 изд.), Эссекс, Великобритания: Elsevier Science Publishers Ltd: 211–229, doi : 10.1016/j.tcs.2006.08.017 , ISSN 0304-3975

[1]