¿Cómo informa la longitud de la salida de un problema su complejidad?

Question

Considerar la Decisión Problema: Subconjunto SUM . Para un conjunto de entrada de enteros, solicita una sí / no contestación a la pregunta de si podemos o no, podemos encontrar un subconjunto de elementos de esta entrada que suma a 0. La salida para este problema es $ o (1) $ y simple (por ejemplo, 1/0). Este problema es NP-Complete , que hasta donde entiendo solo se define para problemas de decisión .

Ahora considere un problema asociado con la suma de subconjunto que solicita de salida todos dichos subconjuntos que suman hasta 0. Hasta lo que entiendo, este es un problema de optimización .

Además, la la salida de este problema podría crecer como $ o (2 ^ n) $ si $ n $ es el tamaño de la matriz de entrada (es decir, la salida crece tan rápido como la cardinalidad del conjunto de potencia de la entrada). Si es así, ¿qué dice esto sobre la clase o de complejidad de este problema de optimización?

En términos generales, ¿el tamaño de la producción de un problema de optimización proporciona un límite inferior más bajo en la complejidad de la optimización o problemas de decisión asociados?

Answer 1

No, no es un problema de optimización.Se necesita al menos un paso de cálculo por bit o palabra de salida (dependiendo del modelo de cálculo), por lo que, dado que la salida puede ser $ \ omega (2 ^ n) $ , eso significa que el tiempo de ejecución del peor de los casos será $ \ omega (2 ^ n) $ , sin importar qué algoritmo use.Por lo tanto, la complejidad es $ \ omega (2 ^ n) $ .

Sí, el tamaño de la salida es un límite inferior en el tiempo de funcionamiento para producir esa salida.