#algorithm #time-complexity #p-np
#алгоритм #сложность по времени #p-np
Вопрос:
Алгоритм должен генерировать все возможные комбинации из заданного списка (пустой набор исключен).
list => [1, 2, 3]
combinations => [{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}]
Этот алгоритм потребует O (2 n) времени для генерации всех комбинаций. Однако я не уверен, сможет ли улучшенный алгоритм снизить эту временную сложность. Если существует улучшенный алгоритм, пожалуйста, поделитесь своими знаниями!
В случае, когда требуется O (2 n), что является экспоненциальным, я хотел бы получить некоторое представление о том, к какому классу принадлежит этот алгоритм P, NP, NP-Complete или NP-Hard. Заранее спасибо 🙂
Комментарии:
1. Если целью кода является создание списка всех возможных комбинаций, то невозможно сделать лучше, чем O (2 ^ n) . Сложность алгоритма никогда не может быть меньше размера выходных данных.
Ответ №1:
P, NP, NP-complete и NP-hard — это все классы задач принятия решений, ни одна из которых не содержит проблем, связанных с недвоичным выводом (например, эта задача перечисления).
Часто люди в разговорной речи ссылаются на проблемы в FNP как на NP. Эта проблема также не в FNP, потому что длина выходной строки для отношения должна быть ограничена некоторой полиномиальной функцией входной длины. Это может быть сложно с точки зрения FNP, но мы попадаем в сорняки, которые не покрывает даже высшее образование CS. Стоит спросить на CS Stack Exchange, если вам все равно.
Ответ №2:
Эта проблема ни в одном из них, кроме, возможно, NP-hard .
Это не в P, потому что для этого нет алгоритма полиномиального времени. Вы не можете сгенерировать экспоненциальное количество вещей за полиномиальное время.
Это не в NP, потому что нет алгоритма полиномиального времени для проверки ответа. Вы не можете обработать экспоненциальное количество вещей за полиномиальное время.
Это не в NP-complete, потому что все в NP-complete должно быть в NP, а это не так.
Аргумент в пользу того, что он находится в NP-hard, выглядит следующим образом. Вы можете сказать все, что хотите, о членах пустого множества. Включая то, что они заставляют обезьян вылетать из вашего носа и могут решить любую задачу в NP за полиномиальное время. Итак, если бы мы могли найти полиномиальное решение, мы могли бы быстро решить любую NP-задачу, и, следовательно, она соответствует определению NP-hard. Но это бесполезно — мы знаем, что полиномиального решения не существует.
Комментарии:
1. Я не думаю, что последний пункт правильный. Даже если мы на мгновение проигнорируем, что NP-hard касается проблем с принятием решений, оракул O (1) для проблемы, подобной описанной в вопросе, не окажет никакой помощи при полиномиальном решении NP-задач.
2. @ADdV Оракул O (1) также не поможет заставить обезьян вылететь из вашего носа. Дело в том, что вы можете сказать все, что хотите, о членах пустого множества.
3. Я, конечно, хочу сказать, что задача является NP-сложной тогда и только тогда, когда машина oracle с oracle для задачи может решить любую задачу в NP за полиномиальное время. Ничто в определении NP-hardness не касается обезьян и носов.