2023-01-17から1日間の記事一覧
はじめに 定期テストに向けて、Karp's Reduction の流れに沿って、諸々の問題の NP 完全性を示すことができるように勉強する必要が生じた。 ここでは、ナップサック問題が弱 NP 完全問題であることを、Partition が弱 NP 完全問題であることを利用して、証明…
はじめに 定期テストに向けて、Karp's Reduction の流れに沿って、諸々の問題の NP 完全性を示すことができるように勉強する必要が生じた。 ここでは、ナップサック問題が弱 NP 完全問題であることを、Partition が弱 NP 完全問題であることを利用して、証明…