推 pinglunliao:兩個意思我都有，但偏重後者 2) 太困難了．．． 12/01 01:06
推 nayd:記得是 nondeterministic polynomial time Turing machine 01/02 14:37
推 superlai:中文的意思大概是..無法在線性時間內解出答案的問題?這樣 01/07 10:34
※ 引述《[馬路探子]》之銘言：
: ───────────────────────────────────────
: ◆ 投票中止於: 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)