查看: 5487|回复: 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 ) 936487697

GMT+8, 2024-11-25 13:26 , Processed in 0.035453 second(s), 8 queries , Redis On.

账号		自动登录	找回密码
密码			立即注册