algorithm - 多項式時間でパーティションを設定するにはどうすればよいですか？

Question

多項式時間で集合の分割を半分に解く可能性について読んだばかりです。しかし、それを行うためのアルゴリズムが見つかりませんでした。

2つの質問があります：

1. そのアルゴリズムはどこで入手できますか？
2. NP問題を多項式時間でどのように解決できるのでしょうか。

Answer 1

正確にどこでそれを読んだかを言及する必要があります。多項式近似アルゴリズム、または疑似多項式の正確なアルゴリズム (動的プログラミングの疑似多項式ソリューションが存在します) に出くわした可能性がありますが、多項式の正確なアルゴリズムではないことは間違いありません。分割問題は NP 問題であり、多項式ではないためです。 P=NP でない限り、アルゴリズムで解くことができます。

Answer 2

できません。これは NP 完全であり、これまでのところ、NP 完全問題を P 時間で解く方法はありません。