Вопросы по теме 'np-complete'
как первые NP-полные задачи оказались NP-полными?
Из статьи в Википедии о NP-Complete:
«Самый простой способ доказать, что какая-то новая проблема является NP-полной - сначала доказать, что она находится в NP, а затем свести к ней некоторую известную NP-полную задачу»
Я почти уверен, что...
6824 просмотров
schedule
04.03.2023
Легче ли решить этот вариант задачи о сумме подмножеств?
У меня проблема, связанная с проблемой суммы подмножества , и мне интересно, облегчают ли эти различия различия, т. Е. разрешима в разумные сроки.
Учитывая значение V, размер набора L и последовательность чисел [1, N] S, сколько подмножеств...
7729 просмотров
schedule
02.10.2022
Является ли это допустимой задачей математического выражения P или NP?
Этот вопрос чисто из любопытства. Я не хожу в школу на лето и собирался реализовать алгоритм, чтобы решить эту проблему просто для удовольствия. Это привело к вышеупомянутому вопросу, насколько сложна эта проблема?
Задача: вам дан список...
1503 просмотров
schedule
05.05.2023
Найти набор чисел в одном наборе, который в сумме дает число в другом
Для игры, которую я делаю, у меня есть ситуация, когда у меня есть список чисел, например [7, 4, 9, 1, 15, 2] (названный для этого A ), и другой список чисел, например [11, 18, 14 , 8, 3] (имя B ). Цель состоит в том, чтобы найти все комбинации...
1412 просмотров
schedule
14.04.2023
доказательство NP-полное
Привет, ребята, у меня есть вопрос. Мне интересно, знает ли кто-нибудь, как это доказать. Вот вопрос: показано, что задача о сумме подмножеств является NP-полной. На вход подается последовательность положительных чисел w1, ... ,wn, W, где W —...
266 просмотров
schedule
30.06.2022
Np-снижение твердости
Если я хочу показать, что проблема является np-сложной, можно ли использовать существующую np-сложную задачу несколько раз? Например, используйте гамильтоновский цикл n раз в графе, где n - количество вершин? Или мне нужно преобразовать граф во...
316 просмотров
schedule
01.08.2023
Предложите алгоритм (график - возможно, NP-Complete)
Это сеть городов, соединенных дорогами разной протяженности.
Путешественник хочет путешествовать на своей машине из одного города в другой. Однако он не хочет минимизировать пройденное расстояние; вместо этого он хочет минимизировать расходы на...
462 просмотров
schedule
22.06.2023
раскраска графа и NP-полнота
У меня проблемы с пониманием NP-полноты раскраски графа.
Если я предполагаю жадную стратегию раскраски ( http://en.wikipedia.org/wiki/Graph_coloring#Greedy_coloring ) с DFS, то, похоже, я смогу оптимально раскрасить графики. Может ли кто-нибудь...
974 просмотров
schedule
31.12.2023
Показ того, что версия решения NP-полного языка является NP-полной.
Скажем, вам задана задача комбинаторной оптимизации A. Предположим, что WLOG представляет собой проблему клики.
Как я могу показать, что если клика NP-полная, то версия решения клики NP-полна, где версия решения, конечно же, является следующей...
291 просмотров
schedule
09.06.2022
Класс NP: почему выводится полиномиальная длина?
Чтобы задача соответствовала классу NP:
Решение задачи должно иметь полиномиальную выходную длину и
Решение должно быть верифицируемым за полиномиальное время.
Каково значение полиномиальной выходной длины?
PS: я думаю, что длина...
295 просмотров
schedule
07.12.2023
NP-Complete и некоторые решения задач на графе?
Мы знаем об NP-Complete, NP-Hard и NP Class. Я хочу подытожить несколько советов по следующей задаче, взятой из середины экзамена MIT в 2008 году.
Решение Вариант какой из следующих задач для связного неориентированного взвешенного графа G...
186 просмотров
schedule
17.09.2022
Сложность некоторых задач в NP?
Я хочу обобщить некоторые проблемы на сложности. Какие из них можно решить в поливремени?
I) поиск максимального подполного графа данного графа = проблема клики
II) выбрать некоторые элементы среди n объектов, в которых заданы...
100 просмотров
schedule
12.10.2023
Длина решения суммы подмножества
Я использую следующую логику для решения проблемы суммы подмножества, как описано в этом вопросе: Total сумма из множества (логика) . Он работает и каждый раз дает мне одно случайное решение, проблема в том, что мне нужны только решения с...
83 просмотров
schedule
25.07.2023
Сложность суммы подмножества с несколькими целями
Является ли следующая проблема в NP-Complete или P? Входные данные : набор S положительных целых чисел {a1, a2, ..., an) и положительное целое число M Вопрос : существует подмножество S' множества S такое, что сумма всех элементов S' равна M-1,...
279 просмотров
schedule
15.04.2022
Трудности в понимании логики сбалансированного разбиения
Я решал проблему сбалансированного разбиения по этой ссылке . В этом вопросе мы должны разделить массив на равные части так, чтобы разница между их суммой была наименьшей. Итак, решение, которое я нашел, заключается в рассмотрении всех случаев,...
85 просмотров
schedule
24.12.2022
Разница между C-SAT и SAT?
В чем именно разница между этими двумя NP-полными задачами? Мне кажется, что они оба спрашивают, может ли быть удовлетворена логическая формула (т.е. результат 1), но одна находится в контексте схемы, а другая - просто формулы. Однако нельзя ли...
345 просмотров
schedule
03.10.2022
Докажите, что конкретная проблема решения является NP-полной
Дано: граф G
Ввод: k
Возврат: «ДА», если существует набор из k узлов, такой, что никакие два узла не связаны и никакие два узла не связаны с одним и тем же узлом. Например, если (A, B) и (B, C), то A и C не допускаются в наборе из k узлов. Как...
30 просмотров
schedule
20.01.2023
Как уменьшить k-независимую задачу о множестве до 3-SAT
Итак, я получил этот домашний вопрос, и нас просят свести проблему выполнимости k-независимого набора к 3-SAT набору предложений в конъюнктивной нормальной форме.
Итак, для G (V, E) у нас установлены вершины V = { x1, x2, x3, x4, x5, x6} и...
180 просмотров
schedule
02.11.2022
