2-NEXPTIME-полные задачи

У нас есть проблема, и мы нашли алгоритм, который выглядит как 2-nexptime.

Я хотел бы найти известные 2-nexptime-полные проблемы, чтобы найти нижнюю границу.

В литературе я обнаружил в основном две такие проблемы:

• будет ли PCP как решение размером меньше $2^{2^n}$
• и проблема вспашки для квадрата размера $2^{2^n}$

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

Я не ставлю здесь задачу специально для того, чтобы иметь общее представление о 2-СЛЕДУЮЩЕМ.

Спасибо

Очевидная проблема N2Exp - это, конечно же, проблема принятия слова для недетерминированных машин Тьюринга с ограничением по времени. Использовать это может быть так же трудно / просто, как и 2exp, поскольку моделирование такого вычисления машины Тьюринга по сути также требует от вас определения двойной экспоненциально большой сетки (2exp для многих конфигураций лент памяти длиной 2exp каждая), которая затем заполняется недетерминированным способом. На практике показ нижних границ N2Exp часто сводится к построению такой сетки (и проверке того, что это не дерево или что-то еще с недостаточной структурой). Буква «N» (недетерминизм) часто является неотъемлемой частью проблемы, и ее не так сложно получить, если у вас достаточно большая сетка (если нет, то, возможно, сначала выстрелили бы в 2exp).

Еще одна практическая проблема, связанная с N2ExpTime-завершением, - рассуждение в логиках выразительного описания (DL). В частности, DL$\mathcal{SROIQ}$который лежит в основе стандарта языка веб-онтологий W3C OWL 2, N2ExpTime-complete (Евгений Казаков: RIQ и SROIQ сложнее, чем SHOIQ. KR 2008: 274-284). Теперь это, вероятно, не та проблема, которую вы хотите использовать в сокращениях, поскольку определение логики немного громоздко из-за ее многочисленных функций. Фактическое доказательство нижней границы для$\mathcal{SROIQ}$также было сделано путем сокращения до 2-exp плитки. Тем не менее, в зависимости от вашей проблемы, строительство предоставляется для$\mathcal{SROIQ}$ может быть вдохновляющим, чтобы увидеть, как создать такие большие сетки.

В листе также показан еще один общий шаблон: N2Exp действительно похож на NP, вам просто нужно найти способ очень эффективно кодировать даже более крупные экземпляры проблемы. В принципе, вы можете попытаться решить любую проблему NP. Причина, по которой мозаика хороша, заключается в том, что в этом случае вам нужно только масштабировать размер сетки (что довольно равномерно).

С другой стороны, если ваша проблема возможно только 2ExpTime полной, то вы могли бы уйти с пространственно-ограниченной экспоненциально Переменный машины Тьюринга моделирования. Если у вас есть проблемы с построением сетки 2экспо, но вы можете получить экспоненциальные размеры, то это стоит попробовать.