全解容易（YP）問題——定義：對于非判定性原題，能在多項式時間內給出全部正確解，
例解容易（SP）問題——定義：對于非判定性原題，能在多項式時間內給出至少1個正確解，
判解容易（JP）問題——定義：對于非判定性原題的一個待驗解，能在多項式時間內判定正誤，
驗判（對判定的復驗）容易（CP，俗稱NP）問題——定義：對于判定性原題的一個待驗答案及其證明，或對于非判定性原題的一個待驗解的某種判定及其證明，能在多項式時間內復驗，
驗解對（對解對判定的復驗）容易（CAP）——例：加減乘除、因數分解、簽名
驗更佳（對更佳判定的復驗）容易（CBP）——例：旅行商最優規劃
驗相似（對相似判定的復驗）容易（CCP）——例：圖同構（可能降為CAP）
僅驗相異（僅對相異判定的復驗）容易（CDP）——例：子圖同構（可能降為CAP）
僅驗更劣（僅對更劣判定的復驗）容易（CEP）——例：囚徒困境
僅驗解錯（僅對解錯判定的復驗）容易（CFP）——例：素數判定、素因數分解、階乘
當前知識水平下，全解容易（YP）⊂例解容易（SP）⊂判解容易（JP）⊂驗解對容易（CAP）⊂驗判容易（CP），
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/58138.html
標籤：其他
上一篇：idea 代碼顏色修改