# IA completo

En el campo de inteligencia artificial, los problemas más difíciles son informalmente conocidos como IA-completos o IA-duros, al implicar ven que la dificultad de estos problemas computacionales es equivalente a solucionar el problema central de inteligencia artificial –hacer ordenadores tan inteligentes como personas–, o IA Fuerte. Llamar un problema refleja que no sería solucionado por un algoritmo específico sencillo.
Hipotéticamente, los problemas AI-completos incluyen visión por ordenador, procesamiento de lenguaje natural, y tratar con circunstancias inesperadas mientras se soluciona un problema del mundo real.
Actualmente, los problemas IA-completos no pueden ser solucionados solamente con tecnología de computación moderna, también requieren computación humana. Esta propiedad puede ser útil, por ejemplo para comprobar la presencia de humanos usando CAPTCHAs

## Historia

El término fue acuñado por Fanya Montalvo por analogía con NP-completo y NP-duro en teoría de complejidad, el cual describe formalmente la clase más famosa de problemas difíciles. Los usos tempranos del término están en la disertación de doctorado de Erik Mueller en 1987 y en el Archivo de Jerga de Eric Raymond en el 1991.

## Problemas IA-completos

Hipotéticamente, los problemas IA-completos incluyen:
* Visión de ordenador (y subproblemas como reconocimiento de objetos)
* Comprensión de lenguaje natural (y subproblems como minería de texto, traducción automática, y desambiguación.)
* Tratar con circunstancias inesperadas mientras se soluciona un problema del mundo real, ya sea navegación o planificación o incluso razonamiento hecho por sistemas expertos.

### Traducción automática

Para traducir con exactitud, una máquina tiene que ser capaz de entender el texto. Tiene que ser capaz de seguir el argumento del autor, así que debe tener alguna capacidad de razonar. Tiene que poseer un conocimiento general extenso de modo que sepa de qué está siendo hablado -al menos tiene que estar familiarizado con todos los mismos hechos de sentido común que el traductor humano mediano sabe-. Parte de este conocimiento está en la forma de hechos que puede ser explícitamente representado, pero otra parte es inconsciente y estrechamente ligado al cuerpo humano: por ejemplo, la máquina puede necesitar entender cómo el océano hace sentir a una persona para poder traducir con exactitud una metáfora en el texto. También debe modelar los objetivos, intenciones, y estados emocionales del autor para reproducirlos con precisión en un nuevo idioma. En resumen, se requiere que la máquina posea una gran variedad de habilidades intelectuales humanas, incluyendo razón, conocimiento de sentido común y las intuiciones que subyacen al movimiento y la manipulación, percepción e inteligencia social. La traducción automática, por tanto, se cree que sea IA-completo: puede que requiera IA fuerte para que sea hecho tan bien como los humanos lo pueden hacer.

## Fragilidad del software

Los sistemas de IA actuales pueden solucionar versiones restringidas muy simples de problemas IA-completos, pero nunca en su total generalidad. Cuando investigadores de IA intentan "escalar hacia arriba" sus sistemas para manejar situaciones del mundo real más complicados, los programas tienden a convertirse en excesivamente quebradizo: sin sentido común o una rudimentaria comprensión de la situación fallan tan pronto circunstancias inesperadas fuera del contexto del problema original aparecen. Cuándo los seres humanos tratan con situaciones nuevas en el mundo, son ayudados grandemente por el hecho de que saben qué esperar: saben qué son todas las cosas a su alrededor, por qué están allí, y aproximadamente qué pueden hacer. Pueden reconocer situaciones inusuales y ajustarse en consecuencia. Una máquina sin IA fuerte, no tiene otras habilidades en las cual apoyarse.

## Formalización

La teoría de la complejidad computacional trata con la dificultad relativa de funciones computables. Por definición no cubre problemas cuya solución es desconocida o no ha sido caracterizado formalmente. Dado que muchos problemas de IA no tienen ninguna formalización aún, la teoría de complejidad convencional no permite la definición de IA-completitud.
Para abordar este problema, una teoría de complejidad para IA ha sido propuesto. Está basado en un modelo de computación que divide la carga computacional entre un ordenador y un humano: una parte es resuelta por el ordenador y la otra parte por el humano. Esto está formalizado como una Máquina de Turing asistida por humanos. La formalización define complejidad de algoritmo, complejidad de problema y reducibilidad, la cual permite definir clases de equivalencia.
La complejidad de ejecutar un algoritmo con una máquina de Turing asistida por humanos está dado por un par$\langle \Phi _{H},\Phi _{M}\rangle$, donde el primer elemento representa la complejidad de la parte del humano y el segundo elemento es la complejidad de la parte de la máquina

### Resultados

La complejidad de solucionar los problemas siguientes con una Máquina de Turing asistida por humanos es:
* Reconocimiento óptico de caracteres para texto impreso: $\langle O(1),poly(n)\rangle$
* Prueba de Turing:
** Para una conversación de n-oraciones donde el oráculo recuerda la historia de la conversación (oráculo persistente): $\langle O(n),O(n)\rangle$
** Para una conversación de n-oraciones donde la historia de la conversación tiene que ser retransmitida: $\langle O(n),O(n^{2})\rangle$
** Para una conversación de n-oraciones donde la historia de la conversación tiene que ser retransmitida y la persona toma tiempo lineal para leer la consulta: $\langle O(n^{2}),O(n^{2})\rangle$
* Juego ESP: $\langle O(n),O(n)\rangle$
* Etiquetado de imágenes (basado en el protocolo Arthur–Merlin): $\langle O(n),O(n)\rangle$
* Clasificación de imágenes: humano sólo: $\langle O(n),O(n)\rangle$, y con menos dependencia del humano: $\langle O(\log n),O(n\log n)\rangle$.