Многие считают, что . Однако мы только знаем, что находится на втором уровне полиномиальной иерархии, то есть . Шаг к показу состоит в том, чтобы сначала перевести его на первый уровень полиномиальной иерархии, то есть .BPPPNPBPP=P⊆NP\mathsf{BPP} = \mathsf{P} \subseteq...
Ограниченность недетерминизм связывает функцию g(n)g(n)g(n) с классом языков , принятых ресурсы ограничены детерминированные тьюринговых машинами, чтобы сформировать новый класс - . Этот класс состоит из тех языков, которые принимаются некоторой недетерминированной машиной Тьюринга подчиняющейся...
Рассмотрим недетерминированные конечные автоматы A=(Q,Σ,δ,q0,F)A=(Q,Σ,δ,q0,F)A = (Q, \Sigma, \delta, q_0, F) и функцию f(n)f(n)f(n) . Дополнительно определим Σ≤k=⋃i≤kΣiΣ≤k=⋃i≤kΣi\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i . Теперь давайте проанализируем следующее утверждение: Если...
Пусть L1,L2L1,L2L_1,L_2 будут двумя обычными языками, заданными NFA M1,M2M1,M2M_1,M_2 качестве входных данных. Предположим, мы хотели бы проверить, является ли L1∩L2≠∅L1∩L2≠∅L_1\cap L_2\neq \emptyset . Это можно сделать с помощью квадратичного алгоритма, который вычисляет автомат произведений...
Первоначальная теорема недетерминированной временной иерархии принадлежит Кук (ссылка на С. Кука, иерархия недетерминированной временной сложности , JCSS 7 343–353, 1973). Теорема утверждает, что для любых действительных чисел r1r1r_1 и r2r2r_2 , если 1≤r1<r21≤r1<r21 \le r_1 \lt r_2 то NTIME...
У меня есть два исторических вопроса: Кто первым описал недетерминированные вычисления? Я знаю, что Кук описал NP-полные проблемы, и что Эдмондс предложил, чтобы P-алгоритмы были "эффективными" или "хорошими" алгоритмами. Я искал эту статью в Википедии и пролистал «О вычислительной сложности...
Решение проблемы CNF-SAT можно описать следующим образом: Вход: булева формула в конъюнктивной нормальной форме.ϕφ\phi Вопрос: существует ли присвоение переменной, которая удовлетворяет ?ϕφ\phi Я рассматриваю несколько различных подходов к решению проблемы CNF-SAT с помощью недетерминированной...
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
В теории автоматов (конечных автоматов, автоматов с выталкиванием, ...) и в сложности существует понятие «неоднозначность». Автомат является неоднозначным, если существует слово по крайней мере, с двумя различными принимающими сериями. Машина является неоднозначной, если для каждого слова принятого...
Недетерминированная логическая схема имеет, помимо обычных входов , набор «недетерминированных» входов . Недетерминированная схема принимает вход если существует такой, что выход схемы включен . Аналогично (класс языков, разрешимых схемами полиномиального размера), можно определить как класс...
Недетерминированный Xor автомат (NXA) является синтаксически NFA, но говорят, что NXA принимает слово, если оно имеет нечетное число принимающих путей (вместо хотя бы одного принимающего пути в случае NFA). Легко видеть, что для конечного регулярного языка LLL существует минимальный NFA, который не...
Может ли недетерминизм ускорить детерминистские вычисления? Если да, то сколько? Под ускорением детерминированных вычислений недетерминизмом я подразумеваю результаты вида: DTime(f(n))⊆NTime(n)DTime(f(n))⊆NTime(n)\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n) Например, что-то вроде...
Согласно этой статье , в которой обсуждается недетерминированное расширение гипотезы сильного экспоненциального времени (SETH), «[…] Уильямс недавно показал, что связанные гипотезы о сложности Мерлин-Артура k-TAUT являются ложными». Тем не менее, эта статья цитирует только личное общение. Как...
Доказательство Омер Рейнгольда , что дает алгоритм USTCON (В U ndirected граф со специальными вершинами S и т , они Con подсоединены?) , Используя только logspace. Основная идея состоит в том, чтобы построить график расширителя из исходного графика, а затем выполнить обход в графике расширителя....
Эта статья доказывает, что в игре с дверями и прижимными плитами PSPACE сложно определить, может ли аватар (игрока) достичь определенного места. Это подтверждается сокращением от TQBF , а длина полученных решений экспоненциально зависит от количества универсальных квантификаторов в формуле. Есть ли...
Greibach лихо определил язык , так называемую недетерминированную версию о , таких , что любая КЛЛ является обратной морфической изображение . Существует ли подобное утверждение с DCFL, возможно, с некоторыми ограничениями на допустимые морфизмы?D 2 HЧАСHHD2D2D_2ЧАСHH (См., Например, М. Аутеберт,...
Если мы можем доказать, что , означает ли это, что ?L=PL=P\mathsf{L}=\mathsf{P}NL=NPNL=NP\mathsf{NL}=\mathsf{NP} Я думал, что это так, но я не могу доказать это (также для
Хорошо известно, что вычисление недетерминированной машины Тьюринга (NTM) представляется в виде дерева конфигураций, основанного на начальной конфигурации. Любой переход в программе представлен ссылкой «отец-ребенок» в этом дереве. Подобные деревья также могут быть построены для визуализации...
Есть некоторые проблемы NP-Complete ( , \ mathsf {SUBSETSUM} и т. Д.), О которых известно, что они находятся в \ mathsf {DSPACE (n)} . Как насчет сублинейных пространств?SATSAT \mathsf{SAT} SUBSETSUMSUBSETSUM \mathsf{SUBSETSUM} DSPACE(n)DSPACE(n) \mathsf{DSPACE(n)} Существует ли какая-либо...
Это продолжение недетерминированного ускорения детерминированных вычислений . Возможно ли, что недетерминизм (или, в более общем смысле, чередование) позволил бы общее квадратичное ускорение детерминированных вычислений? Или есть какие-то известные неправдоподобные последствия для чего-то вроде...