Правильно ли я понимаю, что доказательство того, что задача NP завершена, является успехом исследования? Если так, то
Меня интересует следующая проблема: учитывая множество X и подмножества X_1, ..., X_n из X, найдите раскраску элементов X с помощью k цветов, чтобы все элементы в каждом X_i были по-разному окрашены. Более конкретно, я смотрю на случай, когда все X_i имеют размер k. Известно ли это в литературе под...
Понятие полиномиального сокращения времени (сокращения Кука) является абстракцией очень интуитивного понятия: эффективное решение проблемы с использованием алгоритма для другой задачи. Тем не менее, в теории -полнота, понятие N P -hardness захватывается с помощью сокращений (сокращения отображения...
Эта проблема возникла из моего недавнего поста в блоге. Предположим, у вас есть тур по TSP. Является ли он совместным с NP, чтобы определить, является ли он минимальным? Точнее следующая задача NP-полная: Экземпляр: заданный полный граф G с ребрами, взвешенными с положительными целыми числами, и...
Рассмотрим следующую задачу QQQ : Нам дано целое число и k интервалов [ l i , r i ] с 1 ≤ l i ≤ r i ≤ 2 n . Нам также даны 2 n целых чисел d 1 , … , d 2 n ≥ 0 . Задача состоит в том, чтобы выбрать минимальное количество интервалов [ l i , r i ]nnnkkk[li,ri][li,ri][l_i,r_i]1≤li≤ri≤2n1≤li≤ri≤2n1\leq...
Предположим, вам дан связный простой неориентированный граф H. Проблема H-свободного среза определяется следующим образом: Для простого неориентированного графа G существует ли разрез (разбиение вершин на два непустых множества L, R) такой, что графы, индуцированные множествами разрезов (L и R), не...
Недавно я прочитал доказательство, которое намеревалось показать, что проблема была сильно NP-трудной, просто сводя ее (за полиномиальное время) от сильно NP-трудной задачи. Это не имело никакого смысла для меня. Я бы подумал, что вам нужно будет показать, что любые числа, использованные в...
Недавно я столкнулся со следующим вариантом окраски краев. Для связного неориентированного графа найдите раскраску ребер, которая использует максимальное количество цветов, а также удовлетворяет ограничению, согласно которому для каждой вершины ребра, инцидентные используют не более двух...
Я пытаюсь выяснить, есть ли какие-либо общие результаты или примеры, касающиеся NP-полноты проблемы поиска второго решения NP-полной задачи. Точнее, меня интересуют любые проблемы следующего вида: Учитывая решение для экземпляра NP-полной задачи, есть ли решение для ?SSSяяIS'≠ SS'≠SS' \neq SяяI...
Известно, что пересечение трех общих матроидов является NP-трудным ( источником ), что осуществляется посредством сокращения из гамильтонова цикла. Сокращение использует один графический матроид и два матроида связи. Частный случай проблемы, над которой я работаю, может быть решен путем пересечения...
Для простого неориентированного графа GGG найдите подмножество A≠∅A≠∅A\neq \emptyset вершин, такое что для любой вершины хотя бы половина соседей также находится в , иx∈Ax∈Ax\in AxxxAAA размер AAA минимален. То есть мы ищем кластер, в котором по крайней мере половина окрестности каждой внутренней...
Меня интересуют два вопроса относительно контекстно-зависимых языков (CSL) и полноты: Существует ли понятие полноты для CSL и какие языки являются законченными? Существуют ли естественные CSL, которые являются NP-полными? Для 2. я, конечно, могу думать о естественных NP-полных языках, которые...
Предположим , что P ≠ N Pп≠Nп\mathsf{P} \neq \mathsf{NP} . N P INпя\mathsf{NPI} - класс задач в Н ПNп\mathsf{NP} которых нет ни в пп\mathsf{P} ни в Н ПNп\mathsf{NP} -твердых. Вы можете найти список проблем предположительно N P INпя\mathsf{NPI} здесь . Теорема Ладнера говорит нам, что если то...
В задаче прямоугольник упаковки, один дается набор прямоугольников и ограничивающий прямоугольник R . Задача состоит в том, чтобы найти расположение r 1 , … , r n внутри R так , чтобы ни один из n прямоугольников не перекрывался. Как правило, ориентация каждого прямоугольника г я фиксируется. То...
Существует очень мало информации, которую я могу найти по NP-полной задаче решения линейного диофантового уравнения в неотрицательных целых числах. То есть, есть решение в неотрицательном к уравнению 1 х 1 + 2 х 2 + . , , + a n x n = b , где все константы положительны? Единственное заслуживающее...
Я ищу проблемы, которые, как известно, являются NPC для ориентированных графов, но имеют полиномиальный алгоритм для неориентированных графов. Я видел вопрос, касающийся здесь «направленных» проблем, которые проще, чем их «ненаправленный» вариант , но я ищу жесткость на направленной стороне....
Обычно используемые алгоритмы хэширования паролей работают сегодня так: солить пароль и подавать его в KDF. Например, используя PBKDF2-HMAC-SHA1, процесс хеширования пароля DK = PBKDF2(HMAC, Password, Salt, ...). Поскольку HMAC представляет собой двухэтапное хеширование с дополненными клавишами, а...
Наезд набор из семейства является подмножеством из такое , что для . Задача найти минимальное множество попаданий данного семейства NP-трудна в общем, поскольку она обобщает проблему покрытия вершин. Теперь мой вопрос:S= { S1, … , SN}Sзнак равно{S1,...,SN}\mathcal{S} = \{S_1, \dots, S_n\}ЧАСЧАСH⋃Nя...
Я задал этот вопрос о переполнении стека некоторое время назад: Проблема: продажа Боба . Кто-то предложил также разместить здесь вопрос. Кто-то уже задавал вопрос, связанный с этой проблемой, здесь - минимальный вес леса данной мощности - но, насколько я понимаю, это не помогает мне с моей...
Я надеялся, что кто-нибудь сможет объяснить мне, почему именно проблема подмножеств является сильно NP-трудной, в то время как проблема сумм подмножеств является NP-трудной. Подмножество Сумма: Дано и Т , существует ли подмножество X ' такое , что Σ я ∈ Х ' х я = Т .Икс= { х1, . , , ,...