Talk:AI-complete

From Wikipedia, the free encyclopedia
Jump to: navigation, search
          This article is of interest to the following WikiProjects:
WikiProject Computer science (Rated Start-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 
WikiProject Software / Computing  (Rated Start-class)
WikiProject icon This article is within the scope of WikiProject Software, a collaborative effort to improve the coverage of software on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
Taskforce icon
This article is supported by WikiProject Computing.
 

untitled[edit]

I've expanded the etymology of the term. I deleted a paragraph about problems with the AI field. It was correct, but not related to the topic of the page. --LC


I deleted the "MindForth" code, which does not belong here, also known as "example" in previous edits. Montalvo 8 July 2005 05:25 (UTC)


If this term was coined by Fanya S. Montalvo, why is there reference for this author?--84.190.147.182 13:19, 19 October 2005 (UTC)


I'm not an expert in computer AI terminology, but perhaps some parts of this article ought to at least be clarified. The phrase "AI-hard" and a direct reference to "NP-hard" in computational complexity theory makes it sound like an AI-hard problem is one to which every problem in AI (presumably the class of problems that can be solved effectively by strong AI) can be reduced. Yet, problems that are given as examples of AI-complete (therefore AI-hard, I assume?) seem to not have the property of every problem solvable by strong AI being reducible to those problems. For instance, speech recognition cannot be reduced to go-playing in any way I am familiar with. I understand quite well that there is not a perfect analogy between the class NP and the class AI, but perhaps this should be clarified some more in the article? Am I correct to think that the coining of this terminology was more professional humor than anything else? —Preceding unsigned comment added by 165.123.239.160 (talk) 20:25, 14 September 2008 (UTC)


this article has got to be total bs. if this is what the AI community has come down to, God help us... --unsigned

Categories[edit]

Why is this article tagged with Computational complexity theory? It has nothing to do with it. It just borrows from words from complexity theory. This topic would not appear in any text book on complexity theory. I removed the category, but was reverted [1]. --Robin (talk) 14:08, 5 January 2010 (UTC)

Hello, yes I reverted. The reasoning is that the formalisation in the article is a generalisation of conventional computational complexity: it defines a computation as having both human and computer components and there are equivalence classes of these computations. The article Complete (complexity) is in the computational complexity category so AI-complete, as a generalisation, appears (to me) to belong there too. It probably doesn't appear in textbooks because it's quite recent. Disclaimer: I have no connection with this work but think it is an interesting and useful notion. pgr94 (talk) 13:05, 9 January 2010 (UTC)
Hi, thanks for the response. The thing is, that "complete" has an extremely precise mathematical definition on computational complexity theory. Indeed, all of computational complexity theory is very mathematical, and there are no vague notions. AI-complete, on the other hand, is a fairly vague notion, and an informal one at that. There's no mathematical problem that is proven to be AI-complete, and indeed that might not be possible, since the problem "make machines behave like humans" would not even be expressible mathematically. It seems like AI-complete borrows terminology from complexity theory just to indicate the hardness of some AI problems in an informal sense. These problems are not complete in the technical sense of complexity theory. Moreover, "AI" is not a complexity class in complexity theory, unlike NP-complete (related to the class NP (complexity)) or PSPACE-complete (related to the class PSPACE). For all these reasons, I don't think this article should be in Category: Computational complexity theory. --Robin (talk) 14:53, 9 January 2010 (UTC)