全解容易(YP)问题——定义:对于非判定性原题,能在多项式时间内给出全部正确解。

例解容易(SP)问题——定义:对于非判定性原题,能在多项式时间内给出至少1个正确解。

判解容易(JP)问题——定义:对于非判定性原题的一个待验解,能在多项式时间内判定正误。

验判(对判定的复验)容易(CP,俗称NP)问题——定义:对于判定性原题的一个待验答案及其证明,或对于非判定性原题的一个待验解的某种判定及其证明,能在多项式时间内复验。

 

验解对(对解对判定的复验)容易(CAP)——例:加减乘除、因数分解、签名

验更佳(对更佳判定的复验)容易(CBP)——例:旅行商最优规划

验相似(对相似判定的复验)容易(CCP)——例:图同构(可能降为CAP)

仅验相异(仅对相异判定的复验)容易(CDP)——例:子图同构(可能降为CAP)

仅验更劣(仅对更劣判定的复验)容易(CEP)——例:囚徒困境

仅验解错(仅对解错判定的复验)容易(CFP)——例:素数判定、素因数分解、阶乘

 

当前知识水平下,全解容易(YP)⊂例解容易(SP)⊂判解容易(JP)⊂验解对容易(CAP)⊂验判容易(CP)。

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/webzip/p/13679142.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!