Clases de complejidad

En general, una clase de complejidad se define en términos de un tipo de problema computacional, un modelo de computación y un recurso limitado como el tiempo o la memoria. En concreto, la mayoría de las clases de complejidad consisten en problemas de decisión que pueden resolverse con una máquina de Turing y se diferencian por sus requisitos de tiempo o espacio (memoria). Por ejemplo, la clase P es el conjunto de problemas de decisión que puede resolver una máquina de Turing determinista en tiempo polinómico. Sin embargo, hay muchas clases de complejidad definidas en términos de otros tipos de problemas (por ejemplo, problemas de recuento y problemas de funciones) y utilizando otros modelos de computación (por ejemplo, máquinas de Turing probabilísticas, sistemas de prueba interactivos, circuitos booleanos y ordenadores cuánticos).

El estudio de las relaciones entre las clases de complejidad es un área importante de investigación en la informática teórica. A menudo existen jerarquías generales de clases de complejidad; por ejemplo, se sabe que una serie de clases fundamentales de complejidad temporal y espacial se relacionan entre sí de la siguiente manera: NL⊆P⊆NP⊆PSPACE⊆EXPTIME⊆EXPSPACE (donde ⊆ denota la relación de subconjunto). Sin embargo, hay muchas relaciones que aún no se conocen; por ejemplo, uno de los problemas abiertos más famosos de la informática se refiere a si P es igual a NP. Las relaciones entre clases suelen responder a preguntas sobre la naturaleza fundamental de la computación. El problema de P frente a NP, por ejemplo, está directamente relacionado con las cuestiones de si el no determinismo añade alguna potencia de cálculo a los ordenadores y si los problemas que tienen una solución que puede comprobarse rápidamente para comprobar su corrección también pueden resolverse rápidamente.

Tiempo polinómico

La teoría de la complejidad computacional se centra en la clasificación de los problemas computacionales según su uso de recursos, y en la relación de estas clases entre sí. Un problema computacional es una tarea resuelta por un ordenador. Un problema de cálculo se puede resolver mediante la aplicación mecánica de pasos matemáticos, como un algoritmo.

Se considera que un problema es intrínsecamente difícil si su solución requiere recursos importantes, sea cual sea el algoritmo utilizado. La teoría formaliza esta intuición, introduciendo modelos matemáticos de computación para estudiar estos problemas y cuantificando su complejidad computacional, es decir, la cantidad de recursos necesarios para resolverlos, como el tiempo y el almacenamiento. También se utilizan otras medidas de complejidad, como la cantidad de comunicación (utilizada en la complejidad de la comunicación), el número de puertas de un circuito (utilizado en la complejidad de los circuitos) y el número de procesadores (utilizado en la computación en paralelo). Una de las funciones de la teoría de la complejidad computacional es determinar los límites prácticos de lo que los ordenadores pueden y no pueden hacer. El problema P versus NP, uno de los siete problemas del Premio del Milenio, está dedicado al campo de la complejidad computacional[1].

Complejidad algorítmica

ResumenLa mayoría de los estudios sobre la complejidad de los datos se han centrado en caracterizar la complejidad de todo el conjunto de datos y no proporcionan información sobre las instancias individuales. Saber qué instancias están mal clasificadas y entender por qué lo están y cómo contribuyen a la complejidad del conjunto de datos puede mejorar el proceso de aprendizaje y podría guiar el futuro desarrollo de algoritmos de aprendizaje y métodos de análisis de datos. El objetivo de este trabajo es entender mejor los datos utilizados en los problemas de aprendizaje automático identificando y analizando las instancias que son frecuentemente mal clasificadas por los algoritmos de aprendizaje que han demostrado su utilidad hasta la fecha y que se utilizan habitualmente en la práctica. Identificamos las instancias que son difíciles de clasificar correctamente (dureza de las instancias) clasificando más de 190.000 instancias de 64 conjuntos de datos con 9 algoritmos de aprendizaje. A continuación, utilizamos un conjunto de medidas de dureza para entender por qué algunas instancias son más difíciles de clasificar correctamente que otras. Descubrimos que el solapamiento de clases es el principal factor que contribuye a la dureza de las instancias. Intentamos integrar esta información en el proceso de entrenamiento para aliviar los efectos del solapamiento de clases y presentar formas en las que la dureza de las instancias puede utilizarse para mejorar el aprendizaje.

Complejidad Nl

La teoría de la complejidad computacional es un subcampo de la informática teórica uno de cuyos objetivos principales es clasificar y comparar la dificultad práctica de resolver problemas sobre objetos combinatorios finitos – por ejemplo, dados dos números naturales \(n\) y \(m\), ¿son relativamente primos? Dada una fórmula proposicional \(\phi\), ¿tiene una asignación satisfactoria? Si jugáramos al ajedrez en un tablero de tamaño \(n \times n\), ¿tienen las blancas una estrategia ganadora a partir de una posición inicial dada? Estos problemas son igualmente difíciles desde el punto de vista de la teoría clásica de la computabilidad, en el sentido de que todos son efectivamente decidibles. Sin embargo, parecen diferir significativamente en la dificultad práctica. En efecto, si se dispone de un par de números (m, n, 0), es posible determinar su primalidad relativa mediante un método (el algoritmo de Euclides) que requiere un número de pasos proporcional a (log(n)). Por otra parte, todos los métodos conocidos para resolver los dos últimos problemas requieren una búsqueda de “fuerza bruta” a través de una gran clase de casos que aumentan al menos exponencialmente en el tamaño de la instancia del problema.