Re: [資訊] P != NP has been claimed to be proved.
P class 在 NP class 裡頭，
NP 是指 non-deterministic polynomial time
P 則是 deterministic polynomial time
所以很明顯的，P 內的問題都可以在 NP 內解決，
因為 deterministic TM 都可以當作是 non-deterministic TM。
但我們不知道的是到底是不是嚴格包含，還是相等。
至於證明還沒有被完整檢驗，http://tiny.cc/qunlf 有提到一些問題，
甚至包括證明策略可能有問題。別興奮的太早 ...
※ 引述《thomson (完成度 2/5)》之銘言：
: 請問一下
: 這個人證明 P != NP
: 可是我之前看書 書上寫 P \in NP 這應該代表 P ==> NP
: 所以該位人士 應該是證明 NP != P 吧??
: ※ 引述《ypchen (真實的虛幻和虛幻的真實)》之銘言：
: : Dear Colleagues,
: : Please allow me to share this intriguing (and probably very important) news
: : with you:
: : Vinay Deolalikar from HP Labs claimed to prove that P != NP
: : http://gregbaker.ca/blog/2010/08/07/p-n-np/
: : Prof. Stephen Cook said “This appears to be a relatively serious claim
: : to have solved P vs NP.”
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 82.36.219.50
→
08/12 10:35, , 1F
08/12 10:35, 1F
→
08/12 10:36, , 2F
08/12 10:36, 2F
→
08/12 13:50, , 3F
08/12 13:50, 3F
→
08/12 17:12, , 4F
08/12 17:12, 4F
→
08/12 17:13, , 5F
08/12 17:13, 5F
→
08/12 17:13, , 6F
08/12 17:13, 6F
→
08/12 17:14, , 7F
08/12 17:14, 7F
→
08/12 19:15, , 8F
08/12 19:15, 8F
→
08/12 19:15, , 9F
08/12 19:15, 9F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：