Описание тега np-complete

Описание тега Вопросы с тегом
NP-Complete относится к наиболее сложным из известных проблем класса сложности NP. "Задача коммивояжера" - одна из наиболее широко известных задач NP-Complete.
1 ответ

Докажите, что любое минимальное покрытие вершин клики размера n должно иметь ровно n-1 вершин.

Как доказать, что любое минимальное покрытие вершин клики размера n должно иметь ровно n-1 вершин? Спасибо
18 апр '14 в 15:19
1 ответ

Проблемы НП могут быть решены в детерминистически-экспоненциальное время?

Любая проблема в NP может быть решена за детерминированное экспоненциальное время, или мы можем сказать, что любой язык в NP может быть решен с помощью алгоритма, работающего за время 2^O(n^k), т. е. NP ⊆ EXP неформально говоря, мы просто пробуем ка…
19 ноя '13 в 14:53
1 ответ

Можно ли найти вероятность решения NP-полных задач?

Название охватывает весь вопрос. Можно ли получить функцию, позволяющую с уверенностью сказать, что предложенное решение NP-полной задачи имеет процентную вероятность быть правильным?
07 фев '14 в 10:24
1 ответ

Измерение сложности NP-комплектного

Например, известно, что проблема решения с заданным покрытием является NP-полной проблемой. Входными данными этой проблемы является юниверс U, семейство S подмножеств U и целое число k (). Одна вещь, с которой меня смущает то, что если мы допустим k…
06 янв '14 в 07:33
2 ответа

Доказательство NP-полноты клика + независимый граф набора

"Докажите, что NP-Complete определяет заданные входные данные G и k, имеет ли G как клику размера k, так и независимый набор размера k. Обратите внимание, что это 1 проблема, а не 2; ответ - да, если и только если G имеет оба этих подмножества." Нам…
12 ноя '10 в 01:54
2 ответа

Полиномиальное сокращение времени от NP Complete до других задач

Может кто-нибудь очистить мои сомнения, пожалуйста? Предположим, у меня есть проблема A, которая, как известно, находится в NP-полной. и у меня есть другая проблема B, для которой мы не знаем класс сложности. если я уменьшу A до B за полиномиальное …
18 мар '15 в 13:51
0 ответов

Пытаясь доказать NP-полноту

Представь, у меня есть уравнение, подобное A + B + C + D + E + F + G + H + … = некоторое значение И каждое слагаемое имеет верхний предел A ≤ 500, B ≤ 200, C ≤ 300, D ≤ 600, … Если я хочу, чтобы программа определяла каждую возможную комбинацию слага…
06 сен '15 в 09:58
4 ответа

Может ли NP-Intermediate существовать, если P = NP?

Насколько я понимаю, теорема Ладнера в основном такова: P! = NP означает, что существует набор NPI, где NPI не находится в P, а NPI не является NP-завершенным Что произойдет с этой теоремой, если мы предположим, что P = NP, а не P! = NP? Мы знаем, ч…
11 апр '10 в 21:46
0 ответов

Выполните сокращение от Не Все равно 3SAT до SplittingSet

Я изучал редукцию и видел это упражнение, но не могу его решить. Кто-нибудь может дать мне несколько советов в правильном направлении? Сокращение происходит от Not All Equal 3SAT, где язык = {: T представляет собой набор троек T1, T2, T3... литерало…
14 ноя '18 в 20:13
1 ответ

Проблема назначения с затратами

У меня есть проблема, с которой я застрял, и не могу найти нигде, чтобы начать, поэтому я безнадежно обращаюсь к stackru. проблема хочет, чтобы мы выяснили, является ли он np-сложным или полиномиальным, если его np-hard доказывает np-полноту, иначе …
22 ноя '10 в 22:30
0 ответов

Сокращение от Vertex Cover до LP

Я хочу свести проблему покрытия вершин к конкретной проблеме решения. Это решение проблемы заключается в следующем: У меня есть nxn матрица A, вектор b в R^n и положительное целое число k. Существует ли в R^n вектор x, содержащий не более k ненулевы…
19 мар '17 в 05:54
3 ответа

Необходимо ли, чтобы проблемы NP были решением проблем?

Профессор Тим Рафгарден из Стэнфордского университета, преподавая MOOC, сказал, что решения проблем в классе NP должны быть полиномиальными по длине. Но статья в википедии говорит, что проблемы NP - это проблемы решения. Так какого типа проблемы в о…
10 фев '13 в 15:11
1 ответ

Двойные экспоненциальные проблемы?

Существуют ли какие-либо существенные проблемы в компьютерной науке, которые могут быть решены только в двойном экспоненциальном времени? И если они существуют, то к какому классу проблем они относятся?
11 фев '13 в 17:42
0 ответов

Доказательство Н. П. Полноты проблемы разбиения множества

Я уменьшил проблему суммы подмножеств, чтобы установить проблему с разделами, но не знаю, является ли она правильной, и поэтому мне нужна ваша помощь.МОЙ МЕТОД:В задаче о сумме подмножества мы должны найти подмножество S1 из множества S, чтобы оно с…
29 ноя '18 в 21:17
2 ответа

Разница между C-SAT и SAT?

В чем именно разница между этими двумя NP-полными задачами? Мне кажется, что они оба спрашивают, может ли быть выполнена булева формула (т.е. вывод 1), но один находится в контексте схемы, а другой - просто формула. Однако нельзя ли написать булеву …
21 май '17 в 23:54
0 ответов

Ограниченный гамильтонов цикл

Может кто-нибудь объяснить мне определение ограниченного гамильтонова цикла?Я знаю, что такое гамильтонов путь (и гамильтонов цикл), но у меня возникают проблемы с пониманием, что такое ограниченный гамильтонов цикл. Спасибо.
07 дек '15 в 08:24
1 ответ

Является ли минимизация логических выражений NP-Complete?

Я знаю, что логическая выполнимость является NP-Complete, но является ли минимизация / упрощение логического выражения, что я имею в виду, принимая данное выражение в символической форме и производя эквивалентное, но упрощенное выражение в символиче…
01 мар '09 в 16:42
4 ответа

Является ли обязательным, чтобы "сокращение p‌r‌o‌b‌l bee inm было сделано за полиномиальное время", чтобы оно было завершено NP?

Для того чтобы задача была NP-полной, она должна принадлежать классу NP, и должен быть алгоритм за полиномиальное время, чтобы свести ее к NP-полной задаче. А что если у нас есть только экспоненциальный алгоритм уменьшения времени? Будет ли эта проб…
09 фев '13 в 15:55
0 ответов

Если 01Knapsack является экспоненциальным, почему цикл от 1 до n линейный?

Я прочитал много вопросов здесь на Stackru об этом, и все они делают хорошую мысль: сложность подхода DP к проблеме ранца состоит в O(nW), который экспоненциально по количеству бит в W., если я добавлю еще один бит в W, мне нужно в два раза больше ц…
16 окт '15 в 21:34
0 ответов

Является ли эта задача на взвешенном двудольном графе разрешимой за полиномиальное время или NP-полная?

Я недавно столкнулся с этой проблемой и хочу знать, является ли она NP-полной или разрешимой за полиномиальное время: Для заданного взвешенного двудольного графа G=(V,E), где V можно разбить на два множества A и B, а E - это множество ребер, соединя…
02 сен '14 в 21:25