1. npc問(wèn)題
通俗的理解方式：無(wú)法在多項(xiàng)式時(shí)間內(nèi)求解最域，但是可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證結(jié)果
e.g. ：
驗(yàn)證一個(gè)hash值是否通過(guò)A的私鑰生成復(fù)雜度低茎匠，但是要猜出什么內(nèi)容渐行，通過(guò)A的私鑰生成的hash值會(huì)是B罩句，則是一個(gè)多項(xiàng)式時(shí)間無(wú)法求解的問(wèn)題
1.1 多項(xiàng)式時(shí)間
多項(xiàng)式時(shí)間
算法的復(fù)雜度，我們通常會(huì)說(shuō)O(1) O(n) O(n^2) => 從括號(hào)里看出病线，復(fù)雜度可以用一個(gè)多項(xiàng)式來(lái)表達(dá)的算法，即為多項(xiàng)式時(shí)間算法
多項(xiàng)式：∑n^k 可表達(dá)的復(fù)雜度鲤嫡，比如 e^n是指數(shù)復(fù)雜度送挑，就超越了多項(xiàng)式復(fù)雜度
比如:
遍歷數(shù)組：算法復(fù)雜度為O(n)
二分查找: ?算法復(fù)雜度O(log(n))
冒泡排序：O(n^2)
非多項(xiàng)式時(shí)間
復(fù)雜度無(wú)法通過(guò)多項(xiàng)式表達(dá)，一個(gè)最簡(jiǎn)單的例子暖眼，打印n個(gè)元素的所有組合惕耕，復(fù)雜度為O(n!), 階乘的復(fù)雜度，超越了多項(xiàng)式可表達(dá)的范圍
1.2 P 問(wèn)題
如果一個(gè)問(wèn)題可以找到一個(gè)能在多項(xiàng)式的時(shí)間里解決它的算法诫肠，那么這個(gè)問(wèn)題就屬于P問(wèn)題司澎。（證明：得出完備解決）
我們大多數(shù)實(shí)現(xiàn)的程序和算法，都可以理解為P問(wèn)題栋豫，參見(jiàn)【多項(xiàng)式時(shí)間章節(jié)里面的例子】
1.3 NP問(wèn)題
如果一個(gè)問(wèn)題的解惭缰，能在多項(xiàng)式時(shí)間內(nèi)得到驗(yàn)證，那么這個(gè)問(wèn)題就是NP問(wèn)題
1.4 NP-Hard問(wèn)題
所有的NP問(wèn)題都可以約化到它
約化的概念：解決問(wèn)題B, 就意味著解決問(wèn)題A. 例如：乘法可以約化到加法
理解：無(wú)法在多項(xiàng)式時(shí)間內(nèi)求解的問(wèn)題 （證明一個(gè)問(wèn)題時(shí)NP-hard問(wèn)題笼才，通常是證明它可以解決一個(gè)NPC問(wèn)題）
例子參見(jiàn)文末
1.5 NPC問(wèn)題 NP完備問(wèn)題
同時(shí)滿足下面兩個(gè)條件的問(wèn)題就是NPC問(wèn)題漱受。
1. 它得是一個(gè)NP問(wèn)題；2. 所有的NP問(wèn)題都可以約化到它
理解：無(wú)法在多項(xiàng)式時(shí)間內(nèi)求解，但是可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證結(jié)果
例如這樣一個(gè)問(wèn)題：
已知md5值昂羡，求原內(nèi)容絮记，這個(gè)問(wèn)題只能用窮舉的方法，是一個(gè)無(wú)法在多項(xiàng)式時(shí)間內(nèi)求解的問(wèn)題
但是虐先，我們拿到一個(gè)md5值和一個(gè)內(nèi)容怨愤，卻可以再很有限的計(jì)算代價(jià)下，驗(yàn)證這個(gè)md5是否是這個(gè)內(nèi)容hash得到的
