En la teoría de la complejidad computacional, una clase de complejidad es un grupo de problemas que tienen una dificultad similar para ser resueltos por una computadora. Imagina que tienes muchos rompecabezas; algunos son muy fáciles, otros son difíciles y algunos son casi imposibles. Las clases de complejidad agrupan estos rompecabezas (o "problemas de decisión") según el tiempo o la memoria que una computadora necesita para encontrar la solución.
Un problema de decisión es aquel que tiene una respuesta de "sí" o "no". Por ejemplo, "¿Es este número primo?" o "¿Hay un camino entre dos puntos en un mapa?".
Una clase de complejidad se define así: es el conjunto de problemas de decisión que una computadora puede resolver usando una cierta cantidad de recursos (como tiempo o memoria), dependiendo del tamaño del problema.
¿Cómo se relacionan las clases de complejidad?
En el mundo de la computación, existen muchas clases de problemas, y los científicos las organizan para entender mejor su dificultad. Algunas clases son "subconjuntos" de otras, lo que significa que todos los problemas de una clase más pequeña también pertenecen a una clase más grande.
A veces, sabemos con seguridad que una clase es más pequeña que otra. Otras veces, sospechamos que es más pequeña, pero aún no se ha demostrado. Es como si tuvieras un conjunto de todos los animales y dentro de él, un conjunto más pequeño de mamíferos. Todos los mamíferos son animales, pero no todos los animales son mamíferos.
La siguiente tabla muestra algunas de las clases de problemas más importantes y cómo se relacionan. Las líneas sólidas indican que una clase es un subconjunto seguro de la que está arriba. Las líneas punteadas significan que es un subconjunto, pero no estamos seguros si es estrictamente más pequeña.
|
|
|
 |
|
|
| Lenguaje recursivo enumerable |
|
|
| Problemas muy difíciles de resolver |
|
|
|
|
|
|
|
 |
|
|
|
|
|
|
|
|
|
|
|
|
|
| Gramática sensible al contexto |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Gramática libre de contexto |
|
|
|
|
Ejemplos de clases de complejidad
- La clase NP (que significa "Tiempo Polinómico No Determinista") incluye problemas donde, si alguien te da una posible solución, puedes verificar rápidamente si es correcta. Imagina que te dan la respuesta a un rompecabezas; es fácil saber si encaja, aunque encontrar la respuesta original sea difícil.
- La clase PSPACE (que significa "Espacio Polinómico") agrupa problemas que una computadora puede resolver usando una cantidad de memoria que crece de forma razonable con el tamaño del problema. No importa cuánto tiempo tarde, siempre que no necesite una cantidad infinita de memoria.
Galería de imágenes
-
Línea sólida: indica un subconjunto estricto.
-
Línea punteada: indica un subconjunto cuya relación estricta no está probada.
Véase también
En inglés: Complexity class Facts for Kids
