※ 引述《[马路探子]》之铭言： : ─────────────────────────────────────── : ◆ 投票中止於: 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)