Что означает класс сложности ? Я знаю , что ⊕ P есть класс сложности , который содержит языки А , для которых существует многочлен времени недетерминирован машина Тьюринга M такая , что х ∈ тогда и только тогда число принимающих состояний машины М на входе х нечетно.⊕ P⊕ P⊕P⊕P\oplus P^{\oplus P}⊕...
Я только что прочитал несколько страниц в книге Сипсера «Введение в теорию вычислений о проблеме почтовой корреспонденции» и думаю, что PCP на самом деле находится в NP. Сертификатор составляет: для конфигурации входного ворса конкатенации т 1 , т 2 , . , , , t n как строка t и конкатенация b 1 ,...
Я знаю, что это кажется очень глупым (или слишком очевидным для формулировки) вопросом. Тем не менее, я смущен в какой-то момент. Мы можем показать, что P NPзнак равно== тогда и только тогда, когда сможем разработать алгоритм, который решает любой конкретный случай проблемы в NP за полиномиальное...
Определение: уменьшение Карпа Язык является приводимым по Карпу к языку если существует вычислимая функция за полиномиальное время такая, что для каждого , тогда и только тогда , когда .B f : { 0 , 1 } ∗ → { 0 , 1 } ∗ x x ∈ A f ( x ) ∈...
У нас много проблем, таких как факторизация, которые сильно предположили, но не доказали, что они находятся вне P. Есть ли вопросы с противоположным свойством, а именно, что они сильно предположены, но не доказано, что они находятся внутри...
Вопрос был задан при переполнении стека ( здесь ): Принимая во внимание целое число , распечатать все возможные комбинации целочисленных значений и , которые решают уравнение .NNND A 2 + B 2 + C 2 + D 2 = NA , B , CA,B,CA,B,CDDDA2+ B2+ C2+ D2= NA2+B2+C2+D2=NA^2+B^2+C^2+D^2 = N Этот вопрос, конечно,...
Ниже предположим, что мы работаем с машиной Тьюринга с бесконечной лентой. Объясняя кому-то понятие временной сложности и почему оно измеряется относительно входного размера экземпляра, я наткнулся на следующее утверждение: [..] Например, естественно, что вам нужно больше шагов для умножения двух...
Я видел, как XOR-3-SAT эффективно разрешима (например, см. Раздел «XOR-удовлетворяемость» в статье Википедии для проблемы булевой выполнимости ). Мне интересно основной вопрос: эффективно ли разрешим XOR-k-SAT для формул с различным количеством литералов в предложении? Мне бы очень хотелось узнать,...
Читая некоторые блоги о сложности вычислений (например, здесь ), я усвоил идею, что решить, изоморфны ли две группы, проще, чем тестировать два графа на изоморфизм. Например, на указанной странице говорится, что изоморфизм графов является более общей проблемой, чем изоморфизм групп. Поэтому я...
Мне интересно это на основании нескольких мест в Интернете, которые называют co- серьезной открытой проблемой ... но я не могу найти никаких указаний на то, является ли это тем же, что проблема ...Н П П = Н ПNP=NP=\sf NP=NPNP\sf NPP=NPP=NP\sf...
У меня есть это очень простое «доказательство» для NP = CoNP, и я думаю, что где-то сделал что-то неправильно, но я не могу найти, что не так. Кто-нибудь может мне помочь? Пусть A - некоторая проблема в NP, и пусть M - решающий фактор для A. Пусть B - дополнение, т. Е. B в CoNP. Поскольку M...
Меняется ли сложность задачи с полной NP-сложностью или NP-полной (как, например, определено здесь ), когда ее вход является унарным, а не двоичным? Какая разница, если вход сильно NP-сложной задачи является унарным? Я имею в виду, если я возьму, к примеру, проблему рюкзака со слабой NP-полной, она...
Я пытаюсь составить список алгоритмов / задач, которые являются «исключительно полезными», например, при решении задач, которые «кажутся» очень экспоненциальными по своей природе, но имеют какой-то особенно умный алгоритм, который в конечном итоге решает их. Примеры того, что я имею в виду:...
Я читал о NPC и его связи с PSPACE, и я хотел бы знать, могут ли проблемы NPC быть детерминированно решены с использованием алгоритма с наименьшим требованием к полиномиальному пространству, но потенциально с экспоненциальным временем (2 ^ P (n), где P - полиномиальный). Более того, может ли оно...
Я пытаюсь решить эту проблему, и я действительно борюсь. Монотонная булева формула представляет собой формулу в логике высказываний , где все литералы являются положительными. Например, (x1∨x2)∧(x1∨x3)∧(x3∨x4∨x5)(x1∨x2)∧(x1∨x3)∧(x3∨x4∨x5)\qquad (x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_3 \lor...
Мне интересно, какова сложность определения пустоты для двусторонних DFA? То есть конечные автоматы, которые могут двигаться назад на своей ленте ввода только для чтения. Согласно Википедии, они эквивалентны DFA, хотя эквивалентный DFA может быть экспоненциально больше. Я обнаружил сложность...
У меня возникают проблемы, когда я обдумываю проблемы ПРАЙМ, КОМПОЗИТ, ФАКТОР и их взаимосвязь с точки зрения сложности. Я понимаю, что PRIME был показан в тестом на примитивность AKS, и я считаю, что это работает и для COMPOSITE.PPP Что касается ФАКТОРА, FACTOR={(m,r):∃s such...
Означает ли coNP-полнота NP-твердость? В частности, у меня есть проблема, которую я показал как coNP-полная. Могу ли я утверждать, что это NP-жесткий? Я понимаю, что могу требовать твердости coNP, но я не уверен, является ли эта терминология стандартной. Я согласен с утверждением, что если...
Мне любопытно, есть ли какие-либо полные проблемы в классе сложности Артура-Мерлина. Неизоморфизм графов (GNI) кажется каноническим примером проблемы в AM, но, вероятно, он не полный. Полагаю, мне также интересно, хорошо ли определена «полная» проблема для AM. Так как AM = BP.NP, похоже, что...
Или: нам нужен Руперт, чтобы вообще получать подарки? Помимо вопросов маршрутизации , Санта сталкивается со следующей проблемой (много-много раз): Имея сумку вместимостью ¹ CCC и набор подарков {p1,…,pn}{p1,…,pn}\{p_1, \dots, p_n\} , каждый размером sisis_i , он хочет сделать детей...