Я только что прочитал о возможности разрешить набор разделов наполовину за полиномиальное время. Но я не мог найти алгоритм для этого.Как сделать набор разделов за полиномиальное время?
У меня есть два вопроса:
Вы не можете, это NP-полно и до сих пор не существует возможности решить проблему NP-полной в P-время.
Ну ... Мы ** думаем **, что нет решения полиномиального времени. Если P = NP, то существует алгоритм полиномиального времени! – templatetypedef
вы должны написать NP-complete вместо NP. – sdcvvc
@templatetypedef - отсюда «до сих пор» – zellio
Вы должны упомянуть , где именно вы это читали. Возможно, что вы наткнулись на алгоритм многочлена или псевдо-полином точный алгоритм (псевдополиномиальное решение динамического программирования exists), но определенно не полиномиальный точный алгоритм - поскольку проблема разбиения является NP-проблемой , и ни один полиномиальный алгоритм не может решить его, если только P = NP.
Укажите конкретную проблему, которую вы хотите решить. –
Я хотел бы знать полиномиальный алгоритм для решения набора разделов, который является проблемой NP. – John
Это домашнее задание? – Alex