NP中是否還有每個NP-Easy問題？

可能是我不理解這個權利，但我正在尋找一個圖表，顯示NP-Easy和NP問題集是如何相關的。 NP中的所有NP-Easy問題都是？NP中是否還有每個NP-Easy問題？

2011-12-07 user1069683

http://en.wikipedia.org/wiki/File:P_np_np-complete_np-hard.svg – Jon

感謝Jon。但我正在尋找一些能夠表明NP-Easy與NP的關係。 – user1069683

你正在尋找在錯誤的地方的答案。這是StackOverflow，爲了獲得更多答案，請[StackExchange的網站專注於數學]（http://math.stackexchange.com/），[類似這樣的問題]（http://math.stackexchange.com/問題/ 27032/NP-VS-NP完全問題）。 – Tadeck

在NP中只有檢查部分需要多項式時間：https://stackoverflow.com/questions/8336374/np-complete-problems因此np-easy在np中。

來源

2011-12-07 23:21:41 Bytemain

嗯，他們是在口語意義上。 NP-Easy問題是函數問題，即目標是基於輸入計算輸出，其中NP問題是決策問題，即目標是根據輸入計算布爾結果（是或否）。 NP-Easy就是功能問題NP的等價物，而不是決策問題。換句話說，NP-Easy和NP問題在計算上很難，但是它們是兩個不同的問題，而不是類似的問題類別，因爲NP問題是決策問題，而NP-Easy問題是函數問題。

來源

2011-12-07 23:21:44

NP中是否還有每個NP-Easy問題？

回答

相關問題