作者LFking (小均)
看板CSSE
标题Re: [问题] halt problem 是无解还是NP-hard ?
时间Mon Nov 1 12:15:05 2010
感谢大大的回答,
但NP-hard是否也包含 无解的问题 ？
所谓的NP不就是 有解的题目 但要花很多时间（指数时间）？
※ 引述《LPH66 (-858993460)》之铭言：
: ※ 引述《LFking (小均)》之铭言：
: : 最近小弟在找当机问题(halting problem)的相关资料时
: : 大多数都是用图灵机反证得知能够判断halt的程式不存在(无解
: : 但却也有人说当机问题是NP-hard ?
: : http://en.wikipedia.org/wiki/NP-hard
: : by the way,
: : 那又Windows 7为何可以判断一个程式"可能"已经当机?
: NP-hard 和 undecidability 并不冲突啊...
: 一个问题 H 是 NP-hard 只有要求
: 所有 NP 问题 (或者等价地, 存在某一 NP-complete 问题)可以 reduce 到 H
: 并没有要求 H 要在 NP 当中
: (有要求的话它就是 NP-complete)
: 也就是说一个问题是 NP-hard 只代表它至少和 NP 里最难的那些问题一样难
: 概念上这有点下界的感觉 而上界却是开放的...
: 这样的 H 当然可以是 undecidable 的问题
: 因为 reduce 到 X 的意思是若有一个能够解 X 的黑盒子则我们能解别的东西
: 这 X 可没说是怎麽解的...
: 至於你说的 Win 7 的问题
: 这可以有很多猜测的方法 因为如你所说它所判断的是这程式「可能」已经当机
: 也就是它不一定要百分之百准
: 而 halting problem 却是要求要百分之百答对...
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.133.13.43
1F：推 iamnumbea1:我记得NP的定义不是给定一个解 可以在多项式时间内 11/01 15:49
2F：→ iamnumbea1:验证是否为其解吗 11/01 15:49