應該有唔少人都聽過一個問題:
Is P=NP?

呢個問題值一百萬 如果膠登仔有信心,可以試下交個proof比佢地睇下
http://www.claymath.org/millenium-problems/p-vs-np-problem

好喇,咁究竟呢個問題講緊咩呢?
我地首先要知computational problem可以分為四種難度:
1) Unsolvable Problem(無解,太難唔識計,膠登仔都未必夠打)
2) Intractable Problem(要exponential time先做得完)
3) NP-Problem
4) P-Problem(Polynomial time:好易做既問題,例如排數字sorting,etc.)

NP-Problem就係我地要討論既野:呢類問題好特別,我地可以用Polynomial time既時間去測一個答案o岩唔o岩,但係就唔知有無方法方法用Polynomial time去搵一個答案。
例如:搵因數可能要用好多時間,但係要知a係唔係b既因數,做一次a/b就知

而NP既問題又可以分做兩種:
NP-hard:所有NP問題都可以變做NP-hard既問題。
例如我要搵1001既因數,我可以用1000個true/false statement(由2到1001,如果係1001因數就true,唔係就false),呢個問題就變左一個SAT Problem(可滿足性問題,即係搵true/false)

NP-Complete: 既係NP-Hard,自己又係NP既問題,我地叫佢做NP-Complete

出post經驗尚淺,比較1999,如果有巴打想知多d,我可以再講清楚少少(當然,會有更加多technical既野)


Reference/sauce:
http://en.wikipedia.org/wiki/Boolean_satisfiability_problem
http://blog.xuite.net/jackie.xie/bluelove/7457574