NP, NP-completeness (2)# Thoughts - 思考者
wy
1 楼
有了Turing Machine的概念，偶们就可以定义NP问题了，
P Class: 就是可以在多项式时间内用决定性图灵机解决的
问题的集合。
NP class: 可以在多项式时间内用非决定性图灵机解决的问题
的集合，比如说上例就属于NP集。
一个立即的推论就是P blongs to NP.
同学们广泛知道的计算机界最伟大的一个open problem就是：
Is P=NP?
一个定义：
1. NP-completeness(NP完全）:
一个问题（程序）A in NP,如果所有其它的NP问题
都可以在多项式时间内降解到A,那么我们说A是一个
NP完全问题。这个定义的说明实在太费事，不详细说了，
只说一下它的意义：就是如果我们能够发现一个解决
A的算法属于P,那么我们可以立即下结论说NP==P!
NP完全问题不象大家想象的那样少，相反，非常多，
比如3SAT问题，vertex cover problem,blahblah.
P Class: 就是可以在多项式时间内用决定性图灵机解决的
问题的集合。
NP class: 可以在多项式时间内用非决定性图灵机解决的问题
的集合，比如说上例就属于NP集。
一个立即的推论就是P blongs to NP.
同学们广泛知道的计算机界最伟大的一个open problem就是：
Is P=NP?
一个定义：
1. NP-completeness(NP完全）:
一个问题（程序）A in NP,如果所有其它的NP问题
都可以在多项式时间内降解到A,那么我们说A是一个
NP完全问题。这个定义的说明实在太费事，不详细说了，
只说一下它的意义：就是如果我们能够发现一个解决
A的算法属于P,那么我们可以立即下结论说NP==P!
NP完全问题不象大家想象的那样少，相反，非常多，
比如3SAT问题，vertex cover problem,blahblah.