1.概念
P問(wèn)題就是指該問(wèn)題能在多項(xiàng)式復(fù)雜度內(nèi)解決背稼。
NP問(wèn)題就是指該問(wèn)題能在多項(xiàng)式復(fù)雜度內(nèi)被驗(yàn)證贰军。
復(fù)雜度一般用大寫(xiě)字母O表示，多項(xiàng)式復(fù)雜度記為O(n(^k))蟹肘。
NP-hard問(wèn)題就是比NP問(wèn)題更困難解決的問(wèn)題词疼，通常NP問(wèn)題都可以說(shuō)是NP-hard問(wèn)題，但是不是所有的NP-hard問(wèn)題都是NP問(wèn)題（能否被驗(yàn)證帘腹？）
NP-complete（NPC問(wèn)題）就是既是NP問(wèn)題也是NP-hard問(wèn)題贰盗。
2.常見(jiàn)問(wèn)題復(fù)雜度表（Wikipedia）
3.證明
（1）證明NP問(wèn)題。這個(gè)容易阳欲，即給你一個(gè)結(jié)果舵盈，你能在polynomial的時(shí)間內(nèi)驗(yàn)證該結(jié)果的正確性陋率。
（2）證明NP-hard問(wèn)題。我們要證明一個(gè)問(wèn)題是NP-hard的時(shí)候书释，我們通常要做的是找到一個(gè)已被證明了的NPC問(wèn)題翘贮，并把這個(gè)NPC問(wèn)題歸約到該問(wèn)題上去（即NPC<=NP-hard）。
證明NP-hard問(wèn)題是比較常用的一個(gè)爆惧，去規(guī)約到一個(gè)NPC問(wèn)題（在NPC列表里面找到可以規(guī)約的）
https://en.wikipedia.org/wiki/List_of_NP-complete_problems
（3）證明NP-Complete問(wèn)題狸页。分以下兩步：
3.1????第一步證明這個(gè)問(wèn)題屬于NP；
3.2????第二步扯再，證明這個(gè)問(wèn)題是NP-hard的芍耘。
