Описание тега np-hard
NP-сложные задачи (недетерминированные сложные задачи с полиномиальным временем) - это те проблемы, которые не легче, чем любая проблема в NP; Другими словами, алгоритм NP-сложной задачи может быть использован для решения любой задачи в NP путем преобразования входных данных за полиномиальное время. Проблемы, которые есть как в NP-Hard, так и в NP, известны как NP-Complete.
3
ответа
Решение проблем, которые не могут быть решены даже эффективно?
Как эти проблемы попадают в гобелен из комплектов P, NP, NP-Hard и т. Д.? Я не знаю, существуют ли вообще такие проблемы, но то, что инициировало мой мыслительный процесс, было размышлением о разрешении проблемы коммивояжера: Given a list of cities …
31 мар '14 в 20:02
1
ответ
Как запланировать различные типы досок для формирования мостов
Предположим, мы хотим пройти от места $A$ до места $B$, но между ними есть несколько рек. Чтобы пройти от места $A$ к месту $B$, нам нужно построить мост для каждой реки. У нас есть несколько видов досок. Различные типы досок имеют разную стоимость …
10 сен '13 в 14:55
1
ответ
Измерение сложности NP-комплектного
Например, известно, что проблема решения с заданным покрытием является NP-полной проблемой. Входными данными этой проблемы является юниверс U, семейство S подмножеств U и целое число k (). Одна вещь, с которой меня смущает то, что если мы допустим k…
06 янв '14 в 07:33
6
ответов
3-х мерные алгоритмы упаковки бина
Я столкнулся с проблемой трехмерной упаковки бинов и в настоящее время провожу предварительные исследования относительно того, какие алгоритмы / эвристики дают наилучшие результаты. Так как проблема NP трудна, я не ожидаю найти оптимальное решение в…
03 фев '10 в 13:18
3
ответа
Это проблема линейного программирования?
Я потянул волосы за одну проблему... Общая проблема сложная... но позвольте мне сделать все возможное, чтобы объяснить ту часть, которая действительно имеет значение... У меня есть график, где каждое ребро представляет корреляцию между двумя соедине…
16 июл '11 в 03:58
2
ответа
Путешествующий продавец - приблизительное программное обеспечение онлайн?
Кто-нибудь из вас знает решение для создания даже посредственного решения проблемы коммивояжера. У меня есть 3 человека, которые хотели посетить 31 пункт назначения... Я не знаю, как подойти к этому? Спасибо всем - Максим
21 окт '13 в 17:52
0
ответов
Выполните сокращение от Не Все равно 3SAT до SplittingSet
Я изучал редукцию и видел это упражнение, но не могу его решить. Кто-нибудь может дать мне несколько советов в правильном направлении? Сокращение происходит от Not All Equal 3SAT, где язык = {: T представляет собой набор троек T1, T2, T3... литерало…
14 ноя '18 в 20:13
3
ответа
Связь между NP-трудными и неразрешимыми проблемами
Я немного запутался в связи между неразрешимыми проблемами и трудными проблемами NP. Являются ли трудные проблемы NP подмножеством неразрешимых проблем, или они одинаковы и равны, или они не сопоставимы? Для меня я спорил со своими друзьями, что нер…
08 май '12 в 07:05
7
ответов
Минимальная стоимость сильно связанного орграфа
У меня есть орграф, который сильно связан (то есть есть путь от i до j и от j до i для каждой пары узлов (i, j) в графе G). Я хочу найти из этого графа сильно связный граф, чтобы сумма всех ребер была наименьшей. Иными словами, мне нужно избавиться …
08 окт '09 в 07:05
3
ответа
Почему вершина раскрашивает NP-сложно?
Я читаю алгоритм раскраски вершин. Я вижу документы, объясняющие, как решить проблему, используя BFS (подразумевая, что проблема может быть решена в O(|V|+|E|)). Но я также вижу, что упоминается, что это NP-трудная проблема. Как эти два подходят дру…
15 фев '14 в 14:29
14
ответов
Вы использовали алгоритм коммивояжера для решения проблемы?
Я изучал TSP в колледже в контексте NP Полнота. У меня никогда не было ситуации, когда это применимо к практической проблеме. Небольшое исследование показывает, что он использовался, чтобы выбрать самый дешевый путь для перемещения сверла, в котором…
05 ноя '08 в 00:56
1
ответ
Уменьшает ли P или NP экземпляр до NP-Complete этот экземпляр также NP-Hard?
Если Задача X, лежащая в P или NP, может быть уменьшена до NP-Complete, является ли эта проблема X автоматически проблемой NP-Hard?
25 май '18 в 14:10
3
ответа
Честное разбиение множества S на k разбиений
Существует множество S, содержащее N целых чисел, каждое со значением 1<=X<=10^6. Проблема состоит в том, чтобы разбить множество S на k разделов. Значение раздела - это сумма элементов, присутствующих в нем. Разделение должно быть выполнено таким о…
23 июн '11 в 14:27
1
ответ
Это NP завершено?
Решение проблемы: для заданного графа G и чисел "a", "b" необходимо ответить, существует ли набор вершин "a", совокупная окрестность которых имеет размер, по крайней мере, "b". Как мы покажем, что эта проблема NPC?
23 апр '17 в 00:42
2
ответа
Это проблема NP?
Я недавно прочитал статьи о NP и P. Таким образом, проблема поиска комбинаций данного слова является проблемой NP? Например, данное слово anto, результат может быть anot, toan и так далее. Как я узнал, всякий раз, когда мы можем проверить решение пр…
19 мар '11 в 17:54
2
ответа
Можно ли использовать алгоритм 1 аппроксимации для нескольких задач NP-Hard?
Так как любая проблема NP Hard может быть сведена к любой другой проблеме NP Hard путем сопоставления, мой вопрос на 1 шаг вперед; например, каждый шаг этого алгоритма: может ли он быть сопоставлен с другим NP сложным? заранее спасибо
06 май '13 в 09:40
1
ответ
Что вы называете свойством списка, который описывает степень, в которой он содержит дубликаты?
У меня есть функция, которая выбирает декартовы произведения списков так, чтобы количество повторяющихся элементов было наибольшим: import Data.List (nub) f :: Eq a => [[a]] -> [[a]] f xss = filter ((==) minLength . length . nub) cartProd wher…
13 фев '17 в 18:33
0
ответов
Max Flow и NP, нужны эксперты, чтобы проверить этот вызов?
Я вижу этот вопрос о проблемах NP и нуждаюсь в некоторых деталях? Я изучаю NP, P и NP-Complete на вычислительном курсе, и застрял в одном определении: у нас есть пример, чтобы определить, есть ли в NP или нет: Нахождение максимального потока в сети.…
19 апр '15 в 05:14
1
ответ
np-hard -closure
if l1 is in NP-HARDтак что для каждого L2!= пустое множество, l1*l2 is in np-hard, когда: l1*l2={(w1,w2) , w1 in L1 and w2 in L2} Это правда или ложь и почему? Я не могу это одобрить, но я также не нахожу контрпример.
24 июн '12 в 14:11
0
ответов
TSP-OPTIMIZE - это NP-эквивалент или строго NP-жесткий? Ищете хорошую цитату
Я задаюсь вопросом, является ли TSP-OPTIMIZE NP-эквивалентным, как утверждает вики-доказательство, или оно строго NP-сложное. Чтобы уточнить, я говорю о проблеме оптимизации, которая заключается в поиске кратчайшего обхода для данного графика. Редак…
15 сен '18 в 19:27