c********t
发帖数: 5706 | 1 这章看得我一头雾水。
能快速解决的是P, 不能是NP。但怎么判断一个问题是NPC？ |
K*********n
发帖数: 2852 | 2 什么公司会问这个啊……似乎没见过这样的题啊，可能我做题太少。
【在 c********t 的大作中提到】
: 这章看得我一头雾水。
: 能快速解决的是P, 不能是NP。但怎么判断一个问题是NPC？
|
c********t
发帖数: 5706 | 3 哦，看书复习，想速成，这章和做题关系不太大，但是interview中如果能指出一个问
题是不是NPC，应该能加分.
【在 K*********n 的大作中提到】
: 什么公司会问这个啊……似乎没见过这样的题啊，可能我做题太少。
|
l*****a
发帖数: 14598 | 4 注意，只要答对基本题，基本上offer就没问题了
【在 c********t 的大作中提到】
: 哦，看书复习，想速成，这章和做题关系不太大，但是interview中如果能指出一个问
: 题是不是NPC，应该能加分.
|
K*********n
发帖数: 2852 | 5 我现在OPT已经开始了，所以难题和不常用的问题比如NP之类的，我就不怎么看了。这不
是高考，考到一个点不会就挂了。找工作，不会的话，大不了这个公司不去了。多数公
司问的都是基本题，各种数据结构和算法熟练了就行了。我现在就满足个会写DP问题…
…多的不看了。
【在 l*****a 的大作中提到】
: 注意，只要答对基本题，基本上offer就没问题了
|
l*****a
发帖数: 14598 | 6 hehe
你这个满足点还真挺高。。。
这不
【在 K*********n 的大作中提到】
: 我现在OPT已经开始了，所以难题和不常用的问题比如NP之类的，我就不怎么看了。这不
: 是高考，考到一个点不会就挂了。找工作，不会的话，大不了这个公司不去了。多数公
: 司问的都是基本题，各种数据结构和算法熟练了就行了。我现在就满足个会写DP问题…
: …多的不看了。
|
K*********n
发帖数: 2852 | 7 嗨，就是说DP题知道怎么写，真写起来，稍微复杂点的还是毫无把握啊
【在 l*****a 的大作中提到】
: hehe
: 你这个满足点还真挺高。。。
:
: 这不
|
t********e
发帖数: 1169 | 8 playable, non-playable character
你想必知道P不等于NP这个题目吧？”汤川从他背后出声说。
石神转身。
“对于数学问题，自己想出答案，和确认别人说的答案是否正确，哪一种比较简单，或
者困难到何种程度——这是克雷数学研究所悬赏征求解答的问题之一。”
石神重新面对桌前。
数学很像寻宝，他想。必须先看清该从哪一点进攻，思索通往解答的挖掘路径，然后按
照计划逐步拟定数式，得到线索。如果什么都没得到，就得更改线路。只要这样埋头苦
干，有耐心、但却大胆地走下去，最后就能找到从未被人发掘过的宝藏——也就是正确
解答。
如果用这个比喻，那么鉴证别人的解法，就好像只是沿着别人挖掘的路径前，感觉上进
似乎很简单。但实际上并非如此。如果沿着错误线路前进，找到假宝藏做出某种结论，
有时要证明那个宝藏是假的，会比寻找真宝藏更困难。所以才会有人提出P不等于NP这
种令人束手无策的问题。
汤川推理出石神是嫌犯时：
汤川耸耸肩，皱起鼻子。
“也许会那样吧。对了，我想到一个新的数学问题，有空时你先想想看好吗？”
“是什么题目？”
“拟一个无法解答的问题，和解答那个问题，何者比较困难，不过答案绝对存在。怎样
，你不觉得很有意思吗？”
“的确是耐人寻味的题目。”石神凝视着汤川，“我会好好想想。”
汤川点个头，旋即转身，迈步走向马路。
后来汤川点破谜底时：
汤川轻轻摇头，和草薙相对而坐。
“最后一次见到石神时，他问了一个数学问题。是P不等于NP这个问题。自己想出解答
，和判断别人说的解答是否正确，何者比较简单——这是个著名的难题。”
草薙皱起眉头。
“那是数学吗？怎么听起来像是哲学。”
“你知道吗？石神向你们提出了一个解答，也就是这次的自首、供述内容。这个自白怎
么看都只能说正确无误的解答，是他充分发挥脑力想出来的。如果就这么乖乖地照单全
收，那就表示你们输了。照理说，这次应该轮到你们全力以赴，判断他提出的答案是否
正确。你们正受到来自他的挑战和考验。”
“所以我们不是做了各种采证了吗？”
“你们正在做的，只是按照他的证明方法走。你们该做的，是探寻有没有别的答案。除
了他提出的答案之外别无可能——唯有证明到这个地步，才能断言那个答案是唯一的答
案。” |
n******n
发帖数: 567 | 9 很显然么，游戏里面的人物都是npc。已经好久没有听过这么亲切的单词了。。。。。 |
c********t
发帖数: 5706 | 10 看完更晕
【在 t********e 的大作中提到】
: playable, non-playable character
: 你想必知道P不等于NP这个题目吧？”汤川从他背后出声说。
: 石神转身。
: “对于数学问题，自己想出答案，和确认别人说的答案是否正确，哪一种比较简单，或
: 者困难到何种程度——这是克雷数学研究所悬赏征求解答的问题之一。”
: 石神重新面对桌前。
: 数学很像寻宝，他想。必须先看清该从哪一点进攻，思索通往解答的挖掘路径，然后按
: 照计划逐步拟定数式，得到线索。如果什么都没得到，就得更改线路。只要这样埋头苦
: 干，有耐心、但却大胆地走下去，最后就能找到从未被人发掘过的宝藏——也就是正确
: 解答。
|
c********t
发帖数: 5706 | 11 K.O. U
【在 n******n 的大作中提到】
: 很显然么，游戏里面的人物都是npc。已经好久没有听过这么亲切的单词了。。。。。
|
t********e
发帖数: 1169 | 12 不是做理论的，尝试解释一下， 理论大牛别笑
P跟NP是关于决定性问题(Decision problem)的分类， 有些决定性归于p类， 有些归于
np类. 决定性问题就是些回答是yes/no的问题。
关于一个决定性问题， 比如说旅行推销员问题，人们既关心要多久才能”找到“一个
正确解， 也关心给定一种解法， 多久才能”验证“这个解法是否正确。
如果一个决定性问题的正确解可以在多项式时间内“找到”，那就是属于p类问题
如果能够在多项式时间内”验证“一个解法是否是这个决定性问题的正确解， 那就属
于np问题 |
