Вопросы об отношениях между классами сложности.
Задача 3SUM пытается идентифицировать 3 целых числа из набора размера такого что .a,b,ca,b,ca,b,cSSSnnna+b+c=0a+b+c=0a + b + c = 0 Предполагается, что не существует лучшего решения, чем квадратичное, то есть . Или, по-другому: .o(n2)o(n2)\mathcal{o}(n^2)o(nlog(n)+n2)o(nlog(n)+n2)\mathcal{o}(n...
Если бы кто-то создал универсальный квантовый компьютер, это имело бы какое-то значение для проблемы P против
Этот вопрос был перенесен из теоретического обмена стеков информатики, поскольку на него можно ответить в обмене стеков информатики. Migrated 7 лет назад . В этой статье в Википедии о проблеме Клика в теории графов вначале говорится, что проблема нахождения клики размера K в графе G является...
Возможно ли, что и мощность совпадает с мощностью ? Или означает, что и должны иметь разные мощности?P≠NPP≠NP\mathsf{P} \not = \mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}P≠NPP≠NP\mathsf{P} \not =
Пусть А сводится к B, т.е. . Таким образом, машина Тьюринга приема имеет доступ к оракулу для . Пусть машина Тьюринга, принимающая будет а оракул для будет . Типы скидок:A≤BA≤ВA \leq BAAABВBAAAMAMAM_{A}BВBOBОВO_{B} Сокращение Тьюринга: может сделать несколько запросов к .MAMAM_{A}OBОВO_{B}...
Я читал в Stack Overflow вопрос о том, является ли NP- трудным перечисление всех простых циклов в графе, содержащем определенный узел, и мне пришло в голову, что я не могу придумать какой-либо существующий класс сложности, который хорошо подходит для разговор о проблемах в форме «перечислите все...
У меня есть ряд связанных вопросов по этим двум темам. Во- первых, большинство текстов сложности только замазывать класс NCNC\mathbb{NC} . Есть ли хороший ресурс, который более подробно освещает исследования? Например, то, что обсуждает все мои вопросы ниже. Кроме того, я предполагаю, что...
Я пытаюсь понять доказательство теоремы Карпа-Липтона, изложенное в книге «Вычислительная сложность: современный подход» (2009). В частности, в этой книге говорится следующее: Теорема Карпа-Липтона Если NP P ∖ p o l y , то PH = Σ p 2 .⊆⊆\subseteq P∖polyP∖polyP_{\backslash poly} =Σp2=Σ2p= \Sigma^p_2...
Один студент недавно попросил меня проверить доказательство твердости NP для них. Они выполнили сокращение в соответствии с: Я уменьшаю эту проблему P′п'P' которая, как известно, является NP-полной, к моей проблеме (с многократным уменьшением многократного числа), поэтому является NP-трудной.PпPPпP...
Из того, что я прочитал в preliminary version of a chapter of the book “Lectures on Scheduling” edited by R.H. M¨ohring, C.N. Potts, A.S. Schulz, G.J. Woeginger, L.A. Wolsey, to appear around 2011 A.D. Это определение PTAS : Схема аппроксимации полиномиального времени ( PTAS ) для задачи - это...
Я в некотором роде новичок, но очень интересуюсь областью вычислений и теории сложности, и я хочу разъяснить свое понимание того, как классифицировать проблемы и насколько сильно проблемы связаны с машиной, используемой для их решения. Мое понимание Стандартная машина Тьюринга - машина Тьюринга,...
Мне интересно это на основании нескольких мест в Интернете, которые называют co- серьезной открытой проблемой ... но я не могу найти никаких указаний на то, является ли это тем же, что проблема ...Н П П = Н ПNP=NP=\sf NP=NPNP\sf NPP=NPP=NP\sf...
Мне любопытно, есть ли какие-либо полные проблемы в классе сложности Артура-Мерлина. Неизоморфизм графов (GNI) кажется каноническим примером проблемы в AM, но, вероятно, он не полный. Полагаю, мне также интересно, хорошо ли определена «полная» проблема для AM. Так как AM = BP.NP, похоже, что...
Что означает класс сложности ? Я знаю , что ⊕ P есть класс сложности , который содержит языки А , для которых существует многочлен времени недетерминирован машина Тьюринга M такая , что х ∈ тогда и только тогда число принимающих состояний машины М на входе х нечетно.⊕ P⊕ P⊕P⊕P\oplus P^{\oplus P}⊕...
Как я понимаю, задача присваивания находится в P, поскольку венгерский алгоритм может решить ее за полиномиальное время - O (n 3 ). Я также понимаю, что задача присваивания - это целочисленная задача линейного программирования , но на странице Википедии говорится, что это NP-Hard. Для меня это...
Решение проблемы Учитывая булеву формулу , имеет ли ровно одно удовлетворяющее присваивание?ϕϕ\phiϕϕ\phi можно увидеть в , -hard и -hard. Что-нибудь более известно о его...
Пусть будет некоторой проблемой подсчета, которая известна как # P -Complete .ΠΠ\PiPPP Означает ли это , что является P X -Жесткий (т.е. не PTAS для проблема существует , если P = N P...
Есть ли простой способ понять, почему NP находится в EXPTIME? Мне кажется априори возможным, что может существовать проблема, для решения которой требуется сверхэкспоненциальное время, но решение которой можно проверить за полиномиальное...
Все знают «Garey & Johnson», и я всегда обращаюсь к ним, когда мне нужно выполнить преобразование для доказательства NP-твердости. Однако недавно я нуждался в доказательстве твердости APX, и мне интересно, есть ли подобный (и более современный ...?) Набор проблем, которые, как было показано,...
Для рассуждений о таких вещах, как NP-полнота, мы обычно используем многократные сокращения (т.е. сокращения Карпа). Это приводит к таким картинкам: (по стандартным предположениям). Я уверен, что мы все знакомы с такими вещами. Какую картину мы получаем, если работаем с сокращениями Тьюринга (т. Е....