Вопросы, связанные с NP-твердостью и NP-полнотой.
Норберт Блум недавно опубликовал 38-страничное доказательство того, что . Это правильно?п≠ NпP≠NPP \ne NP Также по теме: где еще (в интернете) обсуждается его правильность? Примечание: фокус этого текста вопроса со временем изменился. Смотрите вопрос комментарии для...
Факторинг и изоморфизм графов - это проблемы в NP, которые, как известно, не находятся в P и не являются NP-полными. Каковы некоторые другие (достаточно разные) естественные проблемы, которые разделяют это свойство? Искусственные примеры, полученные непосредственно из доказательства теоремы...
В настоящее время решается либо полная проблема, либоP S P A C ENPNпNPPSPACЕпSпAСЕPSPACE complete в общем случае невозможно для больших входов. Однако оба они разрешимы в экспоненциальном времени и в полиномиальном пространстве. Поскольку мы не можем создавать недетерминированные или «счастливые»...
Я ищу примеры задач, параметризованных числом , где жесткость задачи немонотонна по k . Большинство проблем (по моему опыту) имеют один фазовый переход, например, k- SAT имеет один фазовый переход от k ∈ { 1 , 2 } (где проблема в P) к k ≥ 3 (где проблема NP- полный). Меня интересуют проблемы, в...
Я сталкивался с полиномиальным алгоритмом, который решает 2SAT. Мне показалось удивительным, что 2SAT находится в P, где все (или многие другие) экземпляры SAT являются NP-Complete. Что отличает эту проблему? Что делает его таким простым (NL-Complete - даже проще, чем...
Несколько задач оптимизации, которые, как известно, являются NP-сложными на общих графах, тривиально разрешимы за полиномиальное время (некоторые даже за линейное время), когда входной граф является деревом. Примеры включают минимальное покрытие вершин, максимальное независимое множество,...
Книга Ароры и Барака представляет факторинг как следующую проблему: FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}Факторингзнак равно{⟨L,U,N⟩|(∃ простое число п∈{L,...,U})[п|N]}\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\} Далее в...
Я думаю о следующей проблеме: я хочу найти регулярное выражение, которое соответствует определенному набору строк (например, действительные адреса электронной почты) и не соответствует другим (недействительные адреса электронной почты). Предположим, что под регулярным выражением мы подразумеваем...
Это кросс-пост от math.stackexchange. Обозначим через FACT целочисленную задачу факторинга: для найдите простые числа и целые числа такие чтоp i ∈ N , e i ∈ N , n = ∏ k i = 0 p e i i .n ∈ N ,n∈N,n \in \mathbb{N},пя∈ N ,pi∈N,p_i \in \mathbb{N},ея∈ N ,ei∈N,e_i \in \mathbb{N},n = ∏Кя =...
Почему большинство людей предпочитают использовать сокращения «один-один» для определения NP-полноты вместо, например, сокращений
Учитывая новую проблему в , истинная сложность которой находится где-то между и являющейся NP-полной, я знаю два метода, которые можно использовать, чтобы доказать, что решить эту проблему сложно:NPNP\mathsf{NP}PP\mathsf{P} Покажите, что задача является GI-полной (GI = Изоморфизм графов) Покажите,...
Марк Доминус собрал несколько примеров сокращения за полиномиальное время от различных задач NP-hard до сопоставления с «регулярным выражением» . Предвидение проверок за полиномиальное время не является огромным скачком. Как вы можете проиллюстрировать класс NP-complete студентам или друзьям в...
У меня есть исторический вопрос. Я пытаюсь определить ссылку на тот факт, что 3-окрашиваемость графиков (альтернативно, окрашиваемость для заданного k \ geq 3 ) является NP-трудной.ККkk ≥ 3К≥3k\geq 3 Заманчивым ответом является «оригинальная статья Карпа», но это не так. Вот сканирование:...
Любое натуральное число может рассматриваться как битовая последовательность, поэтому ввод натурального числа аналогичен вводу последовательности 0-1, поэтому проблемы с NP-заполнением с натуральными входами, очевидно, существуют. Но есть ли естественные проблемы, то есть те, которые не используют...
Пусть обозначает (решение) задачу в NP, а # X обозначает ее счетную версию.ИксXXИксXX При каких условиях известно, что «X является NP-полным» ⟹⟹\implies "#X # P-complete"? Конечно, существование экономного сокращения - одно из таких условий, но это очевидно и единственное условие, о котором я знаю....
Были два вопросы недавно спросил о cs.se , которые были либо связанные или имели особый случай , эквивалентный следующему вопросу: Предположим, у вас есть последовательность из n чисел, такая что ∑ n i = 1 a i = n ( n + 1 ) . Разложите его в сумму двух перестановок, π и , из , так что...
Имеет ли смысл рассматривать категорию всех NP-полных задач с морфизмами как сокращение временного промежутка между различными экземплярами? Кто-нибудь когда-либо публиковал статью об этом, и если так, где я могу найти...
Мы знаем, что (см., Например, теоремы 1 и 3 из [1]), грубо говоря, при подходящих условиях функции, которые могут быть эффективно вычислены машиной Тьюринга за полиномиальное время («эффективно вычисляемое»), могут быть выражены полиномиальными нейронными сетями. с разумными размерами, и, таким...
Читая статью «Пора ли объявить победу в подсчете сложностей?» в блоге «Потерянное письмо Годеля и P = NP» они упомянули дихотомию для CSP. После некоторой ссылки, поиска в Google и википедирования, я наткнулся на теорему Ладнера : Теорема Ладнера: если , то в N P ∖ P существуют проблемы , которые...
Я нашел эту статью очень интересной. Подводя итог: здесь обсуждается, почему на практике вы редко находите наихудший случай проблемы NP-полной. Идея в статье заключается в том, что экземпляры обычно либо сильно недооценены, либо сильно перенапряжены, и то, и другое относительно легко решить. Затем...