※ 引述《[馬路探子]》之銘言： : ─────────────────────────────────────── : ◆ 投票中止於: Thu Nov 30 18:58:41 2006 : ◆ 票選題目描述: : (枯水期期間, 辦個投票提升一下人氣 XD) : 近來發現身旁的朋友們對 NP 這個詞有很多神奇的理解, : 想知道大家的 complexity/automata 老師是不是常常請假... : (作答時請勿偷看隔壁小朋友的考卷 XD) : ◆投票結果:(共有 18 人投票,每人最多可投 11 票) : 選 項 總票數 得票率 得票分布 : NP 是指 non-polynomial time 7 票 38.89% 13.46% ^^^^^^^^^^^^^^^^^^^ 嘻, 第一題就被我騙到了 :P 標準錯誤答案 XD 明天再來詳細說明 : NP 是指 nondeterministic decidable 9 票 50.00% 17.31% 這個是定義 (至少有一半的人都對了, 可喜可賀 XD) : NP 是指 deterministic verifiable 4 票 22.22% 7.69% 另一種定義法, 但跟前一個是可以互證得出的 : NP 是指 nonsolvable problem 3 票 16.67% 5.77% 呃, 照定義來說, NP 是 decidable , 所以是 solvable 的 ^^; : NP = P 2 票 11.11% 3.85% 呃, 據信是錯的, 但尚證不出來 XD : NP != P 6 票 33.33% 11.54% 據信是對的, 但尚證不出來 XD 證出來就可以拿 Fields Medal 或 Turing Award 了吧 XD : NP 是 P 的子集合 2 票 11.11% 3.85% 基於前兩點和下一點, 目前無法得知 XD : NP 是 P 的母集合 12 票 66.67% 23.08% 是的. NP 是 non-determinitic polynomial-time (Turing)decidable, P 是 deterministic polynomial-time (Turing)decidable, 所以只要是 P 裡的問題, 都在 NP 裡 : 啊? 什麼是 NP? 2 票 11.11% 3.85% : 啊? 什麼是 complexity? 2 票 11.11% 3.85% : 啊? 什麼是 automata? 3 票 16.67% 5.77% :P : ─────────────────────────────────────── : ◆ 使用者建議： : ○使用者 pinglunliao 的建議： : NP = Not Problem 呃, 是指 1) 太簡單了, 根本不是問題 還是 2) 太困難了, 這東西怎麼可以拿出來考人? 冏rz : ○使用者 PsMonkey 的建議： : 囧... 我絕對不是那個全部都投的人... : 不過，我真的不知道我的演算法怎麼過的，連老師是誰都忘了 可能是靠直覺就過的吧:P : ○使用者 yoco315 的建議： : 隨便亂猜最快樂 O_Q XD : ─────────────────────────────────────── : ◆ 總票數 = 52 票 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 71.136.238.36 ※ 編輯: march20 來自: 71.136.238.36 (11/30 19:22) ※ 編輯: march20 來自: 71.136.238.36 (11/30 19:31)