Descargo de responsabilidad: actualmente soy un estudiante en un campo de entrenamiento de Ciencia de datos, y aún no nos hemos metido en algoritmos. Esto es solo algo con lo que me tropecé mientras investigaba en mi propio tiempo. Pensé que era un tema interesante. Definitivamente no es un profesional o experimentado con algoritmos en absoluto todavía. Con suerte lo estaré pronto.
desde mi comprensión básica, creo que todos estos Términos se ocupan de la notación Big-O para algoritmos. Con suerte, puedo cubrir esto de una manera muy comprensible.,
breve resumen, Big-O es una medida de la rapidez con la que un algoritmo ejecuta o resuelve un problema (tenga en cuenta que es el límite superior de la duración del tiempo de ejecución).
P, NP, NP-Hard y NP-Complete son clases en las que cualquier problema caería o se clasificaría.
problemas P (polinomios)
los problemas P se refieren a problemas donde un algoritmo tomaría una cantidad de tiempo polinómica para resolver, o donde Big-O es un polinomio(es decir, O(1), O(n), O (n2), etc). Estos son problemas que se considerarían ‘fáciles’ de resolver, y por lo tanto generalmente no tienen tiempos de ejecución inmensos.,
problemas NP (polinomios no deterministas)
los problemas NP fueron un poco más difíciles de entender para mí, pero creo que esto es lo que son. En términos de resolver un problema NP, el tiempo de ejecución no sería polinomio. Sería algo como O (n!) o algo mucho más grande. Sin embargo, a esta clase de problemas se le puede dar una solución específica, y comprobar la solución tendría un tiempo de ejecución polinomial. Un ejemplo que me ayudó a entender esto un poco mejor fue un juego de Sudoku.,
para resolver todo este rompecabezas, el algoritmo tendría que verificar cada matriz 3×3 para ver qué números faltan, luego cada fila, luego cada columna, y luego asegurarse de que no haya repeticiones de ningún dígito del 0 al 9. Esto se vuelve más complejo porque el número de dígitos que faltan es inconsistente en cada fila, columna y matriz (es decir, la matriz superior izquierda carece de 4 dígitos mientras que la matriz superior derecha carece de 8 dígitos). Resolver este problema no tendría un tiempo de ejecución polinómico., Sin embargo, si alimentara este rompecabezas con una posible solución, sería mucho menos complejo verificar si hay alguna repetición en las filas, columnas y matrices. Esta es una comprobación simple que tendría un tiempo de ejecución polinomial.
En esencia, los problemas de la clase NP no tienen un tiempo de ejecución polinomial para resolver, sino que tienen un tiempo de ejecución polinomial para verificar soluciones (difícil de resolver, fácil de verificar una respuesta dada).
reducción
realmente no puedo explicar esto fuera de usar ejemplos, así que: tenemos dos problemas, A y B, y sabemos que el problema B es un problema de clase P., Si el problema A se puede reducir, o convertir en problema B, y esta reducción toma una cantidad de tiempo polinómica, entonces podemos decir que A es también un problema de clase P (A es reducible a B).
Este concepto es importante de entender para las otras dos clases de problemas.
problemas NP-Hard
un problema se clasifica como NP-Hard cuando un algoritmo para resolverlo puede traducirse para resolver cualquier problema NP. Entonces podemos decir, este problema es al menos tan difícil como cualquier problema NP, pero podría ser mucho más difícil o más complejo.,
NP-problemas completos
NP-problemas completos son problemas que viven en las clases NP y NP-Hard. Esto significa que los problemas NP-completos pueden ser verificados en tiempo polinómico y que cualquier problema NP puede ser reducido a este problema en tiempo polinómico.
a continuación se muestra un diagrama de venn de los diferentes espacios de clase.,
Esperamos que este podría haber aclarado las cosas acerca de este tema. Obviamente, tengo conocimientos muy limitados. Simplemente pensé que era interesante hablar de esto y parece que, incluso a un alto nivel, esto es bastante confuso.