У меня есть сильно связанный орграф (т. е. существует путь от i к j и от j к i для каждой пары узлов (i, j) в графе G). Я хочу найти из этого графа сильно связный граф, у которого сумма всех ребер наименьшая. Другими словами, мне нужно избавиться...

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

Я знаю, что если я сведу NP-полную проблему к неизвестной проблеме P , тогда я уверен, что P сам по себе NP-завершен. И я знаю, что если я сведу Проблему P к NP-полной проблеме, вывода не будет. Итак, я хочу привести пример, чтобы показать, что...

Почему NP-хард не равен NP-полному? Мое неформальное понимание используемых определений: NP - все задачи, которые можно проверить за полиномиальное время NP-complete - все задачи NP и NP-сложные NP-сложный - по крайней мере, такой же...

Если L2 является NP-полным и L1 ≤p L2, я могу видеть, что L1 является NP в любой момент времени. И я считаю, что L1 может быть сложным для NP (хотя и не всегда). Теперь мой вопрос: кажется, что в некоторых случаях NP hard можно свести к NP. Я...

Предположим, у меня есть случайная последовательность ( упорядоченный массив ), которая содержит n положительное число с плавающей запятой. Как найти подпоследовательность размера k так, чтобы минимальное расстояние между всеми парами поплавков...