欧卡2中文社区

 找回密码
 立即注册

QQ登录

只需一步,快速开始

需要三步,才能开始

只需两步,慢速开始

玩欧卡就用莱仕达V10方向盘欧卡2入门方向盘选莱仕达V9莱仕达折叠便携游戏方向盘支架欢迎地图Mod入驻
查看: 5369|回复: 0
收起左侧

[学习交流] NP难和NP完全的定义

[复制链接]
知行 发表于 2013-1-10 13:16 | 显示全部楼层 |阅读模式

NP困难: NP-hard
NP: Non-deterministic Polynomial(非确定型多项式)

NP问题: 用非确定性图灵机能在多项式时间内验证的一类问题.
NP困难问题: 若NP中的每个问题R都能多项式归约到S,则S是NP困难问题.
NP完全问题: 若NP中的每个问题R都能多项式归约到S且S是NP问题,则S是NP完全问题.
从上面定义可知,NP困难问题可以是NP完全问题,也可以不是NP完全问题.但NP完全问题一定是NP困难的.

联系我们|手机版|欧卡2中国 ( 湘ICP备11020288号-1 )

GMT+8, 2024-3-29 09:14 , Processed in 0.033202 second(s), 9 queries , Redis On.

Powered by Discuz! X3.4

Copyright © 2001-2023, Tencent Cloud.

快速回复 返回顶部 返回列表