送交者: steven 于 2010-03-29, 18:52:42:

回答: NP-hard includes EXPTIME (Note that I didn't say NP-complete) 由 自如 于 2010-03-29, 18:16:00:

• What did I say that is not true? Note that I said NP-hard, not NP. - 自如 (373 bytes) 2010-03-29, 19:10:05 (427093)
  • generally when we say NP, means problems can be solved - steven (276 bytes) 2010-03-29, 19:51:09 (427101)
    • Sure, no disagreement here - 自如 (222 bytes) 2010-03-29, 20:27:24 (427120)
      • Yes, that has to do with polynomial time turing reduction. - steven (585 bytes) 2010-03-29, 20:54:00 (427135)
        • I actually asked about a different thing, but it doesn't matter :) - 自如 (126 bytes) 2010-03-29, 23:07:55 (427193)
          • you meant the name NP-Hard? It is the official name. (无内容) - steven (0 bytes) 2010-03-30, 00:22:13 (427199)
  • The problem in NP-Hard has to be solvable in poly-time with an oracle machine. - steven (159 bytes) 2010-03-29, 19:34:35 (427096)
    • Another problem due to definition :) - 自如 (97 bytes) 2010-03-29, 19:48:16 (427100)

加跟贴