Origen de la frase "en el polinomio de tiempo'

Question

¿Cuál es el origen y el contexto de la frase 'solucionable en el polinomio tiempo' en ciencias de la computación? Se relacionan con la noción de "polinomios" en matemáticas?

Answer 1

En la teoría de la complejidad, hablamos acerca de los algoritmos en términos de las funciones que describen su tiempo de ejecución. Si dejamos $n$ el número de variables y afirmar que un algoritmo se ejecuta en "$f(n)$ vez:" lo que queremos decir es que la función que describe el tiempo de ejecución del algoritmo (módulo estándar suposiciones y generalizaciones), crece de manera similar a $f(n)$ en el sentido de que sus proporciones tiene un límite finito como $n\to\infty$.

Se define un problema se pueda resolver en el polinomio de tiempo, si existe un algoritmo que resuelve el problema de que el algoritmo se ejecuta en el polinomio de tiempo. Equivalentemente, podemos decir que el algoritmo es $O(n^c)$ algunos $c$ donde $O(x)$ es Big-O Notación

Answer 2

Si el número de pasos necesarios para resolver un problema de tamaño n es limitada por algunos polinomio $f(n)$, entonces se dice que para ser resueltos en el tiempo polinomio. Así que un ejemplo de esto podría ser la de ordenar una lista de números. Si tenemos $n$ números diferentes, entonces el número de pasos necesarios para ordenar la lista sería limitada por $f(n) = n^2$. Usted puede tener más estrictos límites como$f(n) = \frac{n(n+1)}{2}$, pero cuando estamos hablando de los tiempos de ejecución de los algoritmos, básicamente, nos ignorar todas las constantes y los términos de orden inferior.

Answer 3

Se describe que un algoritmo puede resolver un problema en el polinomio de tiempo para un determinado tamaño de entrada. Esta frase es el resultado de la llamada bigO notación. Simplemente busque. Es una parte de la teoría de la complejidad en ciencias de la computación.

En la práctica puede suponer que el tiempo de ejecución de un polinomio de tiempo del algoritmo es aún funcional incluso para las grandes tamaños de entrada. En contraste, los algoritmos de tiempo exponencial tomar mucho más tiempo, incluso para los pequeños tamaños de entrada dado que la función exponencial aumenta muy rápido.

Answer 4

El énfasis en el polinomio tiempo como proxy para la práctica de los algoritmos se puso adelante y popularizado por Edmonds, a pesar de que apareció por primera vez en Cobham, y ahora es a veces llamada la Cobham–Edmonds tesis.