The problem in NP-Hard has to be solvable in poly-time with an oracle machine.
所有跟贴·加跟贴·新语丝读书论坛
送交者: steven 于 2010-03-29, 19:34:35:
回答: What did I say that is not true? Note that I said NP-hard, not NP. 由 自如 于 2010-03-29, 19:10:05:
Problem in EXPTIME does not require that. If NP != P, there are problems which cannot be solved in poly-time. Hence, HP-Hard is definitely a subset of EXPTIME.
所有跟贴:
加跟贴