La trazabilidad de parámetros fijos es algo que he visto mencionado en los procedimientos últimamente. Es la noción de que puede descomponer una entrada en múltiples parámetros que determinan la complejidad de un algoritmo, luego corregir uno de ellos para lograr una complejidad factible, con la esperanza de mantener los otros parámetros lo suficientemente libres como para que el algoritmo restringido sea útil.
Un ejemplo simple de un problema que es manejable con parámetros fijos es encontrar un conjunto independiente de un gráfico. El problema es NP-hard cuando se desconoce el tamaño del conjunto independiente, pero cuando se fija el tamaño del conjunto independiente objetivo en [math] k [/ math], el algoritmo es polinómico con un múltiplo constante de [math] 2 ^ k [/mates].
Aquí hay un ejemplo de un problema real (bisección mínima) que es manejable con parámetros fijos que vi en STOC 2014:
[1311.2563] La bisección mínima es un parámetro fijo manejable.
- ¿Ha habido casos en Informática de no investigadores que contribuyen fundamentalmente a la investigación?
- ¿Qué problemas de visión por computadora son importantes para un equipo de mapas?
- Predicción de tráfico sobre hosts o nodos en la nube: ¿es un tema de tendencia o un área de investigación en la computación en la nube?
- ¿Cuáles son algunos de los buenos proyectos de investigación en informática de la escuela secundaria que puedo hacer?
- ¿Es necesaria una sólida formación en informática para realizar investigaciones en informática teórica?
