◾ AI-Completeness: The Problem Domain of Superintelligent Machines
Roman V. Yampolskiy · 2015
Recent work has attempted to formalize the intuitive notion of AI-Completeness. In particular, three such endowers are worth reviewing next (Yampolskiy 2012a). In 2003, Ahn et al. attempted to formalize the notion of an AI-Problem and the concept of AI-Hardness in the context of computer security. An AI-Problem was defined as a triple: = S D f( , , )P , where S is a set of problem instances, D is a probability distribution over the problem set S, and f : S → {0; 1}* answers the instances. Let δ ∈ (0; 1]. We require that for an α > 0 fraction of the humans H, Prx←D [H(x) = f(x)] > δ. … An AI problem P is said to be (δ, τ)-solved if there exists a program A, running in time at most τ on any input from S, such that Prx←D,r [Ar(x) = f(x)] ≥ δ. (A is said to be a (δ, τ) solution to P .) P is said to be a (δ, τ)-hard AI problem if no current program is a (δ, τ) solution to P . (Ahn et al. 2003, 298).