Как сделать разбиение за полиномиальное время?

Question

Я только что прочитал о возможности решить заданное разбиение на половину за полиномиальное время.Но я не смог найти алгоритм для этого.

У меня есть два вопроса:

1. Где я могу получить этот алгоритм?
2. Как это возможно, проблема NPможно решить за полиномиальное время?

Answer 1

Вы должны упомянуть , где именно вы это прочитали. Возможно, вы наткнулись на алгоритм полинома аппроксимация или псевдополином точный алгоритм (псевдополиномиальное динамическое решение существует ), но определенно нет точный полиномиальный алгоритм - поскольку проблема разбиения является проблемой NP, и никакой полиномиальный алгоритм не может ее решить, если P = NP.

Answer 2

Вы не можете, это NP-завершено, и до сих пор нет способа решить NP-полную проблему за P время.