NP完了またはNP困難？

Question

n個の正の整数のリスト（n偶数）を指定すると、2つのサブリストの整数の和の差が最小になるようにリストを2つのサブリストに分割します。これはNP完全な問題かNP困難な問題か？

Answer 1

TL; DR - これは難しいです。

これは、パーティションの問題の最適化バージョンです。 パーティションの問題は、正の整数のリストが2つのサブセットに分割され、サブセットの合計が等しくなるかどうかを判断することです。 最適化バージョンでは、最小限の相違点を尋ねられます（質問したように）。

パーティションの問題はnp-completeですが、最適化はnpハードです。

あなたはwikiのこれらの問題についてさらに読むことができます： https://en.wikipedia.org/wiki/Partition_problem