614
P NP 問題
單項式，monomial。多項式，polynomial。具體概念見《數學基礎》，https://blog.csdn.net/chuchus/article/details/39136943 。
多項式時間，Polynomial time。在 計算複雜度理論 中，指的是一個問題的計算時間m(n)不大於 問題規模n的多項式倍數。
P問題，Polynomial time problem，多項式時間問題。指這樣一類問題——求解或驗證某個解都為多項式時間。
NP問題，Non-deterministic Polynomial time problem，非確定性多項式時間問題。通俗講，是指那些計算過程比較繁瑣，但驗證答案卻很容易的問題，比如把整數44427進行因數分解，求解過程可能會很費時，但如果告訴你答案是177×251，簡單計算即可驗證答案是對的。
NP-Completed問題，NP-Completed，NP完全問題。指最不可能被化簡為P問題的那類問題。NP完全問題之間是可以互相轉換的，也就意味著隻要一個NP完全問題能在多項式時間內解決，那麼所有的NP完全問題都能在多項式時間內解決。
NP-Hard問題，NP-Hard，NP難問題。指複雜度不小於NP問題中最難的那類問題。
P/NP問題，就是論證P=NP還是P!=NP。如果P!=NP，也就是有些很容易得到驗證的問題不容易被輕鬆地求解，這樣我們的基於非常容易被驗證的素數算法的密鑰係統將保持完全，在影響方麵，雖然這個世界本來是就是假設P!=NP，所以不會出現任何大的變化，但是整個證明的過程將會對其它一些問題的解決會有一定的啟發作用，並對整個科技的發展有一定的推動；如果P=NP的話，每個答案很容易得到驗證的問題也同樣可以輕鬆求解，同時NP完全的問題也能被輕鬆地解決，而整個世界將會發生巨變，比如，所有的基於密鑰的安全係統將失靈；算法的研究可能會轉向圍棋等NP難問題；數學證明可以完全交給計算機來處理；所有人工智能問題都將得到解決，並且機器人能完美模擬人類的行為。
最後更新：2017-04-03 05:40:17