网友：江月 打分：2 [2022-07-27 03:09:21]

20

【P问题：在多项式时间内可以求出解的问题】
【NP问题：在多项式时间内可以证明一个解是对的问题or在多项式时间内可以猜出一个解的问题】
1.所有的P类问题都是NP问题
所有的P类问题都是NP问题的意思是：P属于NP，P是NP的子集
能多项式地解决一个问题，必然能多项式地验证一个问题的解（意思是，既然正解都出来了，验证任意给定的解也只需要比较一下就可以了）。
2.是否所有的NP问题都是P类问题
人们目前想知道想证明的是：是否所有的NP问题都是P类问题
也就是说，集合P与集合NP（把P类问题和NP类问题集合化），现在知道P属于NP，想要知道：是否有P=NP。
【目前的大方向是：P=NP不成立】,也就是，多数人相信，存在至少一个不可能有多项式级复杂度的算法的NP问题
3.NP-compeleted(NP完全问题)
约化（Reducibility，有的资料上叫“归约”）:的含义是，可以用问题B的解法解决问题A，或者说，问题A可以“变成”问题B。
例子1:问题A是求解一个一元一次方程，问题B是求解一个二元一次方程。求解一元一次方程可以约化为求解一个二元一次方程。把问题A转换成问题B，两个问题就等价了。

18  

 
昵称：
打开/关闭本文嗑糖功能
内容：
返回
注: 输入br/即可换行分段,这是对评论的回复，用于读者直接交流，不会对文章的积分造成影响。