В теории сложности вычислений , целая схема является схема модель вычислений , в которой входы схемы являются наборы из целых чисел , и каждый из ворот цепи , вычисляемых либо операции набора или арифметическая операцию на его входных наборах.
В качестве алгоритмической проблемы возможные вопросы состоят в том, чтобы определить, является ли данное целое число элементом выходного узла или две схемы вычисляют один и тот же набор. Разрешимость все еще остается открытым вопросом, но есть результаты по ограничению этих схем. Ответы на некоторые вопросы об этой модели могут послужить доказательством многих важных математических гипотез, таких как гипотеза Гольдбаха .
Это естественное расширение схем над наборами натуральных чисел, когда рассматриваемый набор содержит также отрицательные целые числа, определения, которые не меняются, не будут повторяться на этой странице. Будут упомянуты только различия.
Сложность проблемы членства
Проблема членов является проблема принятия решения, учитывая схему целое число С , вход в схему X , а конкретное число п , является ли целое число п в выходе схемы C при условии , с входным X . Вычислительная сложность этой задачи зависит от типа ворота , разрешенного в цепи C . [1] В таблице ниже суммирована вычислительная сложность проблемы принадлежности для различных классов целочисленных схем. Здесь MF(O) обозначает классы, определенные O-формулами, которые являются O-схемами с максимальным разветвлением 1.
O | MC(O) | MF(O) |
---|---|---|
∪, ∩, -, +, × | NEXPTIME -Жесткий | PSPACE - жесткий |
∪, ∩, +, × | NEXPTIME - завершено | НП-полный |
∪, +, × | NEXPTIME - завершено | НП-полный |
∩, +, × | P - жесткий, в со-НП | L - жесткий, в LOGCFL |
+, × | P - жесткий, в со-НП | L - жесткий, в LOGCFL |
∪, ∩, -, + | PSPACE -полный | PSPACE -полный |
∪, ∩, + | PSPACE -полный | НП-полный |
∪, + | НП-полный | НП-полный |
∩, + | C = L -полный | L -полный |
+ | C = L -полный | L -полный |
∪, ∩, -, × | PSPACE -полный | PSPACE -полный |
∪, ∩, × | PSPACE -полный | НП-полный |
∪, × | НП-полный | НП-полный |
∩, × | ( C = LL) -твердый, в P | L -полный |
× | ( NL - завершеноL) -полный | L -полный |
∪, ∩, - | P -полный | L -полный |
∪, ∩ | P -полный | L -полный |
∪ | NL -полный | L -полный |
∩ | NL -полный | L -полный |