•

Created by Alex_Altair at

Roman V. Yampolskiy proposed a classification in AI-Complete, AI-Hard and AI-Easy problems:

- A problem
*C*is AI-Complete if it has two properties:- It is in the set of AI problems (Human Oracle solvable);
- Any AI problem can be converted into C by some polynomial time algorithm.

- A problem H is AI-Hard if and only if there is an AI-Complete problem C that is polynomial time Turing-reducible to H.

- A problem X is AI-Easy if and only if there exists some AI problem Y such that X is polynomial-time Turing reducible to Y. This means that given an oracle for Y, there exists an algorithm that solves X in polynomial time.

- AI-Complete, AI-Hard, or AI-Easy: Classification of Problems in Artificial Intelligence by Roman V. Yampolskiy

A problem is considered **AI-complete** or **AI-hard** if solving it is equivalent to creating ~~AGI~~Artificial General Intelligence.

For example, natural language processing (or machine translation) is often considered AI-complete because understanding arbitrary language constructs seems to require broad general knowledge. ~~It~~The term was coined by the computer scientist Fanya Montalvo as an analogy with NP-complete, a class of problems in complexity theory. Problems labeled AI-complete like graceful degradation or computer vision tend to be framed at human-level intelligence; there may be many problems that AIs can solve that humans cannot. While mathematical formalizations of the class have been attempted, the term is usually used to communicate the qualitative difficulty of a problem.

A problem is considered **AI-complete** or **AI-hard** if solving it is equivalent to creating AGI. For example, natural language processing (or machine translation) is often considered AI-complete because understanding arbitrary language constructs seems to require broad general knowledge. It was coined by the computer scientist Fanya Montalvo as an analogy with NP-complete, a class of problems in complexity theory. Problems labeled AI-complete like graceful degradation or computer vision tend to be framed at human-level intelligence; there may be many problems that AIs can solve that humans cannot. While mathematical formalizations of the class have been attempted, the term is usually used to communicate the ~~qualitatively~~qualitative difficulty of a problem.

Alex_Altair v1.0.0 (+557) Created page with "{{wikilink}} A problem is considered '''AI-complete''' or '''AI-hard''' if solving it is equivalent to creating [[AGI]]. For example, natural language processing (or machine tran..." 2

A problem is considered **AI-complete** or **AI-hard** if solving it is equivalent to creating AGI. For example, natural language processing (or machine translation) is often considered AI-complete because understanding arbitrary language constructs seems to require broad general knowledge. It was coined by the computer scientist Fanya Montalvo as an analogy with NP-complete, a class of problems in complexity theory. While formalizations have been attempted, the term is usually used to communicate the qualitatively difficulty of a problem.

His AI-Hard if and only if there is an AI-Complete problemCthat is polynomial time Turing-reducible to~~H.~~H.Xis AI-Easy if and only if there exists some AI problemYsuch thatXis polynomial-time Turing reducible to~~Y.~~Y. This means that given an oracle for~~Y,~~Y, there exists an algorithm that solvesXin polynomial time.