В описательной сложности Иммерман имеет Следствие 7.23. Следующие условия эквивалентны: 1. P = NP. 2. Над конечными упорядоченными структурами FO (LFP) = SO. Это можно рассматривать как «усиление» P = NP до эквивалентного утверждения над (предположительно) классами большей сложности. Обратите...
Мы знаем, что первый уровень полиномиальной иерархии (т.е. NP и co-NP) находится в PP, и что . Мы также знаем из теоремы Тоды, что .PP⊆PSPACEPP⊆PSPACEPP \subseteq PSPACEPH⊆PPPPH⊆PPPPH \subseteq P^{PP} Знаем ли мы ? Если нет, то почему с оракулом сильнее ? Возможно ли, что и PP \ nsubseteq PH...
Изменить : Как правильно указал Рави Боппана в своем ответе, и Скотт Ааронсон также добавил еще один пример в своем ответе , ответ на этот вопрос оказался «да» таким образом, которого я вообще не ожидал. Сначала я подумал, что они не ответили на вопрос, который я хотел задать, но, подумав, эти...
Верно ли, что в полиномиальной иерархии существуют проблемы, разрешимые во времени (с помощью чередующейся машины Тьюринга на некотором уровне полиномиальной иерархии), которые не разрешимы в O ( n k - 1 ) на любом уровне полиномиальная иерархия? Другими словами - существует ли теорема временной...
Хорошо известно, что если то иерархия полиномов разрушается и .P = N PP=NP\mathbf{P}=\mathbf{NP}P = P HP=PH\mathbf{P}=\mathbf{PH} Это можно легко понять индуктивно с помощью оракулов. Вопрос в том, почему мы не можем продолжить индуктивный процесс за пределами постоянного уровня чередований и...
Мне нужен список полных языков . Есть две такие проблемы, перечисленные в зоопарке сложности , а именно:Σp2Σ2p\Sigma_2^p Минимальный эквивалент DNF. Учитывая формулу DNF F и целое число k, существует ли формула DNF, эквивалентная F с k или меньшим числом вхождений литералов? Кратчайший имплицит....
Мы знаем, что если то весь PH разрушается. Что если полиномиальная иерархия частично разрушится? (Или как понять, что PH может рухнуть выше определенной точки, а не ниже?)п= NпP=NPP=NP Короче говоря, каковы будут последствия и P ≠ N P ?Nп= с о нпNP=coNPNP=coNPп≠ NпP≠NPP\ne...
Содержится в-между каждым уровнем многочлена иерархии различные классы сложности, в том числе ΔPiΔiP\Delta_i^{\text{P}} , DPDP\text{DP} , BHkBHk\text{BH}_k , и ΣPi∩ΠPiΣiP∩ΠiP\Sigma_i^\text{P} \cap \Pi_i^\text{P} . Из-за отсутствия лучшей терминологии я буду ссылаться на эти и любые другие как...
Известно, что добавление рандомизации с ограниченной ошибкой в PSPACE не добавляет мощности. То есть BPPSAPCE = PSPACE. Известно, что P = BPP известно, но известно, что .Б Пп⊆ Е2∩ Π2Впп⊆Σ2∩Π2BPP\subseteq \Sigma_2\cap \Pi_2 Таким образом, возможно (хотя предполагается, что оно ложно), что...
Теорема PCP утверждает, что каждая проблема решения в NP имеет вероятностно проверяемые доказательства (или, что то же самое, что существует полная и квази-звуковая система доказательств для теорем в NP, использующая постоянную сложность запроса и логарифмически много случайных битов). «Народная...