Algoritmo pseudopolinomio

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 22 de septiembre de 2015; las comprobaciones requieren 5 ediciones .

Algoritmo pseudopolinomial : en la teoría de la complejidad computacional, este es un algoritmo polinomial que exhibe un carácter exponencial solo para valores muy grandes de parámetros numéricos.

Una definición más rigurosa se ve así. Sea alguna función que especifique el valor del parámetro numérico del problema individual . Si hay varios de estos parámetros, se puede tomar como valor el valor máximo o el promedio, y si el problema no tiene ningún parámetro numérico (por ejemplo, coloración de gráficos, ajedrez, etc.), entonces . Un algoritmo se llama pseudopolinomio si tiene una estimación de costos , donde hay algún polinomio en dos variables. ${\ estilo de visualización M (z)}$ $z$ ${\ estilo de visualización M (z)}$ ${\ estilo de visualización M (z) = 0}$ $T_{máx}(z)=O(P(|z|,M(z)))$ $PAGS$

Un algoritmo polinomial también es pseudopolinomio (con un polinomio independiente del segundo argumento), pero no ocurre lo contrario. Los algoritmos pseudopolinómicos, formalmente relacionados con los algoritmos exponenciales, en la práctica funcionan como polinomios en todos los casos, excepto para valores muy grandes del parámetro numérico.

Literatura

Drozdov S. N. Problemas combinatorios y elementos de la teoría de la complejidad computacional: libro de texto. - Taganrog: Editorial de TRTU, 2000. - S. 58.