Wiki define tiempo polinómico como barbecho:
Se dice que un algoritmo es de tiempo polinomial si su tiempo de ejecución está delimitado por una expresión polinomial en el tamaño de la entrada para el algoritmo, es decir, $ T (n) = O (n ^ k) $ para algunos $ k $ constantes
I entender que, en general, la diferencia entre tiempo polinomial y tiempo exponencial es que la función exponencial crece estrictamente más rápido que cualquier función polinomial, asintóticamente ( referencia ).
Estoy tratando de entender el núcleo definición de Tiempo exponencial .
- Qué elementos harán que un algoritmo se ejecute en Tiempo exponencial ?
- ¿Qué cambio debo hacer en la expresión polinomial para convertirlo en Tiempo exponencial ? (Por it me refiero a la definición del algoritmo al principio de la pregunta)
Comentarios
- 1. Haz exponencialmente muchas cosas. 2. Usa el polinomio como la potencia de una base > 1.
- No ' entiendo tu segundo pregunta. Los polinomios son polinomios; exponenciales son exponenciales. Preguntar qué necesitas cambiar para convertir un polinomio en exponencial es como preguntar qué necesitas cambiar para convertir un logaritmo en coseno.
- @DavidRicherby ¿Habrá funciones de tiempo exponenciales si P = NP? ¿Cómo se puede definir una función de tiempo exponencial en términos de expresión polinomial?
- Las funciones exponenciales ciertamente seguirán existiendo si P = NP. Probablemente todavía hay problemas de que ' tomará un tiempo exponencial incluso si P = NP, aunque ninguno me viene a la mente de inmediato. Una función exponencial se puede definir en términos de un polinomio, pero ese polinomio debe ser infinitamente largo; es posible que desee buscar Expansiones de Taylor si ' está interesado en esto.
- @ymbirtt Incluso la versión más sencilla del teorema de la jerarquía de tiempo dice que no existe un algoritmo de tiempo polinomial para ningún problema EXPTIME-complete. Ese ' es un resultado incondicional: no ' t depende de la suposición de que P $ \ neq $ NP.
Respuesta
-
No hay una respuesta fácil para esta, aunque hay señales a las que debe prestar atención . Examinar todos los subconjuntos posibles de un conjunto, por ejemplo, es exponencial, por lo que si tuviera un conjunto de enteros $ \ {x_1, …, x_n \} $, y quisiera verificar cada subconjunto de estos para ver si suman a $ 0 $, tendría que considerar exactamente $ 2 ^ n $ subconjuntos, lo que hace que este método sea un tiempo exponencial. Sin embargo, varias trampas diferentes pueden convertir un algoritmo en tiempo exponencial, así que en lugar de buscar categorías amplias, analice los algoritmos caso por caso.
-
Si un algoritmo toma $ n ^ 2 $ pasos para completarse, entonces es polinomial. Si toma $ 2 ^ n $ pasos, es exponencial. La diferencia es la posición de $ n $. Si algo es $ O (n ^ m) $ por $ n > 1 $, $ m > 0 $, entonces «s polinomio en $ n $ para $ m $ fijos, pero exponencial en $ m $ para $ n $ fijos.
Comentarios
- Cuidado. La función $ n ^ m $ no es ' t polinomio en $ n $ a menos que $ m $ sea una constante. Y, si $ m $ es una constante, no ' no tiene sentido decir que la función es exponencial en esa constante.
- Sí, usted ' tengo razón. Yo ' aclararé eso.
Respuesta
A menudo obtiene un algoritmo de fuerza bruta de tiempo exponencial cuando considera un problema y enumera todo su espacio de búsqueda. Por lo general, pensaría en problemas de subconjunto (en SAT, elegiría un subconjunto de variables establecidas en verdadero), problemas de permutación (en TSP, cada recorrido es una permutación de las ciudades) y problemas de partición (en la coloración del gráfico, está tratando de p Articione los vértices en clases de color). O considere ordenar pares: hay $ n! $ Permutaciones de $ n $ enteros. Revise cada permutación y verifique si está ordenada. Tonto (y lento), pero funciona.
Comentarios
- Aunque tenga en cuenta que $ O (n!) $ Es incluso peor que $ O ( k ^ n) $. Si ' todavía está tratando de aprender sobre la complejidad del tiempo, esto podría ser útil para probarse a sí mismo.