Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

当前知识水平下的问题复杂度分类

阁楼上的瞭望者 2020-09-16 14:58:00 阅读数:3 评论数:0 点赞数:0 收藏数:0

 

全解容易(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