En informática existen algunos problemas cuyas soluciones aún no se encuentran, los problemas se dividen en clases conocidas como Clases de Complejidad . En la teoría de la complejidad, una clase de complejidad es un conjunto de problemas relacionados con la complejidad. Estas clases ayudan a los científicos a agrupar problemas en función de cuánto tiempo y espacio requieren para resolver problemas y verificar las soluciones. Es la rama de la teoría de la computación que se ocupa de los recursos necesarios para resolver un problema.
Los recursos comunes son el tiempo y el espacio, es decir, cuánto tiempo tarda el algoritmo en resolver un problema y el uso de memoria correspondiente.
La complejidad temporal de un algoritmo se usa para describir la cantidad de pasos necesarios para resolver un problema, pero también se puede usar para describir cuánto tiempo lleva verificar la respuesta.
La complejidad espacial de un algoritmo describe cuánta memoria se requiere para que el algoritmo funcione.
Las clases de complejidad son útiles para organizar tipos similares de problemas.
Tipos de clases de complejidad
Este artículo analiza las siguientes clases de complejidad:
- Clase P
- Clase NP
- Clase CoNP
- NP duro
- NP completo
Clase P
La P en la clase P significa tiempo polinomial. Es el conjunto de problemas de decisión (problemas con respuesta “sí” o “no”) que pueden ser resueltos por una máquina determinista en tiempo polinomial.
Características:
- La solución a los problemas P es fácil de encontrar.
- P es a menudo una clase de problemas computacionales que son solucionables y tratables. Tratable significa que los problemas se pueden resolver tanto en la teoría como en la práctica. Pero los problemas que pueden resolverse en teoría pero no en la práctica se conocen como intratables.
Esta clase contiene muchos problemas naturales como:
- Cálculo del máximo común divisor.
- Encontrar una coincidencia máxima.
- Versiones de decisión de la programación lineal.
Clase NP
El NP en la clase NP significa Tiempo polinomial no determinista . Es el conjunto de problemas de decisión que pueden ser resueltos por una máquina no determinista en tiempo polinomial.
Características:
- Las soluciones de la clase NP son difíciles de encontrar ya que están siendo resueltas por una máquina no determinista pero las soluciones son fáciles de verificar.
- Los problemas de NP se pueden verificar mediante una máquina de Turing en tiempo polinomial.
Ejemplo:
Consideremos un ejemplo para comprender mejor la clase NP. Supongamos que hay una empresa que tiene un total de 1000 empleados con identificaciones de empleados únicas. Suponga que hay 200 habitaciones disponibles para ellos. Se debe emparejar una selección de 200 empleados, pero el CEO de la empresa tiene los datos de algunos empleados que no pueden trabajar en la misma habitación por motivos personales.
Este es un ejemplo de un problema NP. Ya que es fácil verificar si la elección dada de 200 empleados propuesta por un compañero de trabajo es satisfactoria o no, es decir, ningún par tomado de la lista de compañeros de trabajo aparece en la lista dada por el CEO. Pero generar una lista de este tipo desde cero parece ser tan difícil que resulta completamente impráctico.
Indica que si alguien puede darnos la solución al problema, podemos encontrar el par correcto e incorrecto en tiempo polinomial. Por lo tanto, para el problema de clase NP, la respuesta es posible, que se puede calcular en tiempo polinomial.
Esta clase contiene muchos problemas que a uno le gustaría poder resolver de manera efectiva:
- Problema de Satisfacción Booleano (SAT).
- Problema de la trayectoria hamiltoniana.
- Coloreado de gráficos.
Clase Co-NP
Co-NP significa el complemento de NP Class. Significa que si la respuesta a un problema en Co-NP es No, entonces hay una prueba que se puede verificar en tiempo polinomial.
Características:
- Si un problema X está en NP, entonces su complemento X’ también está en CoNP.
- Para un problema NP y CoNP, no hay necesidad de verificar todas las respuestas a la vez en tiempo polinomial, es necesario verificar solo una respuesta particular «sí» o «no» en tiempo polinomial para que un problema esté en NP o CoNP.
Algunos problemas de ejemplo para C0-NP son:
- Para comprobar números primos.
- Factorización de enteros.
NP-clase dura
Un problema NP-difícil es al menos tan difícil como el problema más difícil en NP y es la clase de problemas tal que cada problema en NP se reduce a NP-difícil.
Características:
- Todos los problemas NP-difíciles no están en NP.
- Lleva mucho tiempo comprobarlos. Esto significa que si se da una solución para un problema NP-difícil, lleva mucho tiempo comprobar si es correcta o no.
- Un problema A está en NP-difícil si, para cada problema L en NP, existe una reducción de tiempo polinomial de L a A.
Algunos de los ejemplos de problemas en Np-hard son:
- Problema de parada.
- Fórmulas booleanas calificadas.
- Sin ciclo hamiltoniano.
Clase NP-completa
Un problema es NP-completo si es tanto NP como NP-difícil. Los problemas NP-completos son los problemas difíciles en NP.
Características:
- Los problemas NP-completos son especiales ya que cualquier problema en la clase NP puede transformarse o reducirse a problemas NP-completos en tiempo polinomial.
- Si uno pudiera resolver un problema NP-completo en tiempo polinomial, entonces también podría resolver cualquier problema NP en tiempo polinomial.
Algunos ejemplos de problemas incluyen:
- Versión de decisión de 0/1 Mochila.
- Ciclo hamiltoniano.
- Satisfacción.
- cubierta de vértice.
| Clase de complejidad | Característica distintiva |
| PAGS | Fácilmente resoluble en tiempo polinomial. |
| notario público | Sí, las respuestas se pueden verificar en tiempo polinomial. |
| Co-NP | No, las respuestas se pueden verificar en tiempo polinomial. |
| NP-duro | Todos los problemas NP-difíciles no están en NP y lleva mucho tiempo comprobarlos. |
| NP-completo | Un problema que es NP y NP-difícil es NP-completo. |
Para más detalles, consulte: Diseño y Análisis de Algoritmos .