En computación, cuando el tiempo de ejecución de un algoritmo (mediante el cual se obtiene una solución al problema) es menor que un cierto valor calculado a partir del número de variables implicadas (generalmente variables de entrada) usando una fórmula polinómica, se dice que dicho problema se puede resolver en un tiempo polinómico.
Por ejemplo, si determinar el camino óptimo que debe recorrer un cartero que pasa por casas necesita menos de segundos, entonces el problema es resoluble en un "tiempo polinómico".
De esa manera, tiempos de , o son polinómicos; pero no lo es.
Dentro de los tiempos polinómicos, podemos distinguir los logarítmicos , los lineales , los cuadráticos , los cúbicos , etc.
Clases de complejidad
En teoría de la complejidad, la clase de complejidad de los problemas de decisión que pueden ser resueltos en tiempo polinómico calculado a partir de la entrada por una máquina de Turing determinista es llamada P. Cuando se trata de una máquina de Turing no determinista, la clase es llamada NP. Una de las preguntas abiertas más importantes en la actualidad es descubrir si estas clases son diferentes o no. El Clay Mathematics Institute ofrece un millón de dólares a quien sea capaz de responder a esa pregunta.
Diagrama de clases de complejidad. Si P = NP, P contendría las zonas NP y NP-completo.
Los problemas NP-completos pueden ser descritos como los problemas en NP que tienen menos posibilidades de estar en P (Ver NP-completo para una definición precisa). Actualmente los investigadores piensan que las clases cumplen con el diagrama mostrado por lo que P y NP-completo tendrían intersección vacía.
La importancia de la pregunta P = NP radica en que, de encontrarse un algoritmo en P para un problema NP-completo, todos los problemas NP-completos (y por ende, todos los problemas de NP) tendrían soluciones en tiempo polinómico.
Datos:Q846354
Agosto 11, 2021
clase, complejidad, computación, cuando, tiempo, ejecución, algoritmo, mediante, cual, obtiene, solución, problema, menor, cierto, valor, calculado, partir, número, variables, implicadas, generalmente, variables, entrada, usando, fórmula, polinómica, dice, dic. En computacion cuando el tiempo de ejecucion de un algoritmo mediante el cual se obtiene una solucion al problema es menor que un cierto valor calculado a partir del numero de variables implicadas generalmente variables de entrada usando una formula polinomica se dice que dicho problema se puede resolver en un tiempo polinomico Por ejemplo si determinar el camino optimo que debe recorrer un cartero que pasa por N displaystyle N casas necesita menos de 50 N 2 N displaystyle 50N 2 N segundos entonces el problema es resoluble en un tiempo polinomico De esa manera tiempos de 2 n 2 5 n displaystyle 2n 2 5n 4 n 6 7 n 4 2 n 2 displaystyle 4n 6 7n 4 2n 2 o n 2 2 175 displaystyle n 2 2 175 son polinomicos pero 2 n displaystyle 2 n no lo es Dentro de los tiempos polinomicos podemos distinguir los logaritmicos O log n displaystyle O log n los lineales O n displaystyle O n los cuadraticos O n 2 displaystyle O n 2 los cubicos O n 3 displaystyle O n 3 etc Clases de complejidad EditarEn teoria de la complejidad la clase de complejidad de los problemas de decision que pueden ser resueltos en tiempo polinomico calculado a partir de la entrada por una maquina de Turing determinista es llamada P Cuando se trata de una maquina de Turing no determinista la clase es llamada NP Una de las preguntas abiertas mas importantes en la actualidad es descubrir si estas clases son diferentes o no El Clay Mathematics Institute ofrece un millon de dolares a quien sea capaz de responder a esa pregunta Diagrama de clases de complejidad Si P NP P contendria las zonas NP y NP completo Los problemas NP completos pueden ser descritos como los problemas en NP que tienen menos posibilidades de estar en P Ver NP completo para una definicion precisa Actualmente los investigadores piensan que las clases cumplen con el diagrama mostrado por lo que P y NP completo tendrian interseccion vacia La importancia de la pregunta P NP radica en que de encontrarse un algoritmo en P para un problema NP completo todos los problemas NP completos y por ende todos los problemas de NP tendrian soluciones en tiempo polinomico Datos Q846354Obtenido de https es wikipedia org w index php title P clase de complejidad amp oldid 119482296, wikipedia, wiki, leyendo, leer, libro, biblioteca,
