NPでもすべてのNP-Easy問題はNPですか？

Question

私はこの権利を理解していないかもしれませんが、NP-EasyとNPの問題セットがどのように関連しているかを示す図を探しています。すべてのNP-Easy問題はNPであるか？

Answer 1

NPでは、チェック部分のみが多項式時間である必要があります。https://stackoverflow.com/questions/8336374/np-complete-problemsしたがって、np-easyはnpにあります。

Answer 2

はい、彼らは口述的な意味です。 NP-Easy問題は関数問題である。すなわち、目標は入力に基づいて出力を計算することであり、NP問題は決定上の問題である。すなわち目標は入力に基づいて論理結果（yesまたはno）を計算することである。 NP-Easyは、決定問題の代わりに関数問題のNPに相当します。

つまり、NP-EasyとNPの問題は計算上困難ですが、NP問題は決定問題であり、NP-Easy問題は関数問題であるため、2つの異なる問題クラスです。