Вопросы с тегом «p-hardness»

232
Является ли доказательство Норберта Блюма 2017 года, что правильно?

Норберт Блум недавно опубликовал 38-страничное доказательство того, что . Это правильно?п≠ NпP≠NPP \ne NP Также по теме: где еще (в интернете) обсуждается его правильность? Примечание: фокус этого текста вопроса со временем изменился. Смотрите вопрос комментарии для...

128
Проблемы между P и NPC

Факторинг и изоморфизм графов - это проблемы в NP, которые, как известно, не находятся в P и не являются NP-полными. Каковы некоторые другие (достаточно разные) естественные проблемы, которые разделяют это свойство? Искусственные примеры, полученные непосредственно из доказательства теоремы...

66
Являются ли

В настоящее время решается либо полная проблема, либоP S P A C ENPNпNPPSPACЕпSпAСЕPSPACE complete в общем случае невозможно для больших входов. Однако оба они разрешимы в экспоненциальном времени и в полиномиальном пространстве. Поскольку мы не можем создавать недетерминированные или «счастливые»...

60
Параметризованная сложность от P до NP-хард и обратно

Я ищу примеры задач, параметризованных числом , где жесткость задачи немонотонна по k . Большинство проблем (по моему опыту) имеют один фазовый переход, например, k- SAT имеет один фазовый переход от k ∈ { 1 , 2 } (где проблема в P) к k ≥ 3 (где проблема NP- полный). Меня интересуют проблемы, в...

55
Почему 2SAT в P?

Я сталкивался с полиномиальным алгоритмом, который решает 2SAT. Мне показалось удивительным, что 2SAT находится в P, где все (или многие другие) экземпляры SAT являются NP-Complete. Что отличает эту проблему? Что делает его таким простым (NL-Complete - даже проще, чем...

47
NP-сложные проблемы на деревьях

Несколько задач оптимизации, которые, как известно, являются NP-сложными на общих графах, тривиально разрешимы за полиномиальное время (некоторые даже за линейное время), когда входной граф является деревом. Примеры включают минимальное покрытие вершин, максимальное независимое множество,...

45
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]\} Далее в...

43
Является ли нахождение минимального регулярного выражения NP-полной проблемой?

Я думаю о следующей проблеме: я хочу найти регулярное выражение, которое соответствует определенному набору строк (например, действительные адреса электронной почты) и не соответствует другим (недействительные адреса электронной почты). Предположим, что под регулярным выражением мы подразумеваем...

39
Известны ли проблемы PRIMES, FACTORING как P-hard?

Пусть PRIMES (иначе тестирование на примитивность ) будет проблемой: Учитывая натуральное число , является простое число?NNnNNn Пусть FACTORING будет проблемой: Учитывая натуральные числа , с , имеет ли фактор с ?NNnммm1 ≤ m ≤ n1≤м≤N1 \leq m \leq nNNnddd1 < д< м1<d<м1 < d < m Известно...

39
Является ли проблема целочисленной факторизации сложнее, чем факторизация RSA: ?

Это кросс-пост от 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 = ∏Кя =...

36
Методы показа этой проблемы в твердости «подвешенный»

Учитывая новую проблему в , истинная сложность которой находится где-то между и являющейся NP-полной, я знаю два метода, которые можно использовать, чтобы доказать, что решить эту проблему сложно:NPNP\mathsf{NP}PP\mathsf{P} Покажите, что задача является GI-полной (GI = Изоморфизм графов) Покажите,...

34
Ежедневные встречи с NP-полными проблемами

Марк Доминус собрал несколько примеров сокращения за полиномиальное время от различных задач NP-hard до сопоставления с «регулярным выражением» . Предвидение проверок за полиномиальное время не является огромным скачком. Как вы можете проиллюстрировать класс NP-complete студентам или друзьям в...

33
Ссылка для NP-твердости 3-х цветов?

У меня есть исторический вопрос. Я пытаюсь определить ссылку на тот факт, что 3-окрашиваемость графиков (альтернативно, окрашиваемость для заданного k \ geq 3 ) является NP-трудной.ККkk ≥ 3К≥3k\geq 3 Заманчивым ответом является «оригинальная статья Карпа», но это не так. Вот сканирование:...

30
Есть ли естественная проблема на натуральных объектах, которая является NP-полной?

Любое натуральное число может рассматриваться как битовая последовательность, поэтому ввод натурального числа аналогичен вводу последовательности 0-1, поэтому проблемы с NP-заполнением с натуральными входами, очевидно, существуют. Но есть ли естественные проблемы, то есть те, которые не используют...

29
Когда «X является NP-полным» подразумевает «#X является # P-полным»?

Пусть обозначает (решение) задачу в NP, а # X обозначает ее счетную версию.ИксXXИксXX При каких условиях известно, что «X является NP-полным» ⟹⟹\implies "#X # P-complete"? Конечно, существование экономного сокращения - одно из таких условий, но это очевидно и единственное условие, о котором я знаю....

29
Можете ли вы определить сумму двух перестановок за полиномиальное время?

Были два вопросы недавно спросил о cs.se , которые были либо связанные или имели особый случай , эквивалентный следующему вопросу: Предположим, у вас есть последовательность из n чисел, такая что ∑ n i = 1 a i = n ( n + 1 ) . Разложите его в сумму двух перестановок, π и , из , так что...

28
Категория NP-полных задач?

Имеет ли смысл рассматривать категорию всех NP-полных задач с морфизмами как сокращение временного промежутка между различными экземплярами? Кто-нибудь когда-либо публиковал статью об этом, и если так, где я могу найти...

28
Функции, которые неэффективно вычислимы, но обучаемы

Мы знаем, что (см., Например, теоремы 1 и 3 из [1]), грубо говоря, при подходящих условиях функции, которые могут быть эффективно вычислены машиной Тьюринга за полиномиальное время («эффективно вычисляемое»), могут быть выражены полиномиальными нейронными сетями. с разумными размерами, и, таким...

27
Можно ли найти, существует ли последовательность за полиномиальное время в следующей задаче?

Некоторое время я думал о следующей проблеме, и я не нашел ее полиномиального решения. Только грубая четверка. Я тоже пытался свести к этому проблему NP-Complete, но безуспешно. Вот проблема : У вас есть отсортированный набор пар целых положительных чисел....