Agree with the first sentence, but not the second one :)


所有跟贴·加跟贴·新语丝读书论坛

送交者: 自如 于 2010-03-30, 01:00:24:

回答: What you said is incorrect. 由 steven 于 2010-03-30, 00:33:30:

引用:
NP problem is not a research interest of AI and ML people. NP problem is in computational theory, most of the AI and ML people don't care about NP because in AI and ML, problems are not well specified. There is very few problems in AI or ML related to NP.

Indeed it's the comp-theorists who started the research on NP etc and cataloged complexity classes (e.g., complexity zoo). AI/ML people shouldn't be blamed (or credited) for that discovery.

But AI/ML people do care about complexity (or have been suffering from the curse :-). E.g., see the following paper, which proves that inference in Bayesian networks is intractable (exact inference is #P-Complete; Approximate Reasoning is NP-Hard). It is published in Artificial Intelligence, the top journal of AI.

http://l2r.cs.uiuc.edu/~danr/Papers/hardJ.pdf

BTW, I figure out what I meant to ask you below. The better term is intractable. Do you agree? I have been using NP-hard loosely to mean that, but apparently it can cause confusion.




所有跟贴:


加跟贴

笔名: 密码: 注册笔名请按这里

标题:

内容: (BBCode使用说明