GAP (グラフのアクセシビリティの問題) は NP-Complete ですか? それを解決する多項式および非決定論的多項式アルゴリズムがありますが、これは、NP および NP-Hard => NP-Complete であることを示すことによって、NP-Complete であることを示す基本的な方法をオーバーライドする基準ではないと思います。どちらのバージョンも私より年上の学生から聞きました。結局、それは NP-Complete なのか、そうでないのか?
GAP (グラフのアクセシビリティの問題) は NP-Complete ですか? それを解決する多項式および非決定論的多項式アルゴリズムがありますが、これは、NP および NP-Hard => NP-Complete であることを示すことによって、NP-Complete であることを示す基本的な方法をオーバーライドする基準ではないと思います。どちらのバージョンも私より年上の学生から聞きました。結局、それは NP-Complete なのか、そうでないのか?