¿Hay problemas cuya complejidad de caso promedio es la misma que su peor complejidad de caso? ¿Cuáles son las propiedades subyacentes de estos problemas que hacen posible reducir el peor de los casos al caso promedio posible?
11
¿Hay problemas cuya complejidad de caso promedio es la misma que su peor complejidad de caso? ¿Cuáles son las propiedades subyacentes de estos problemas que hacen posible reducir el peor de los casos al caso promedio posible?
Respuestas:
Este tipo de problema ha sido objeto de bastante estudio. Puede encontrar referencias buscando en Google la auto-reducibilidad aleatoria, y el artículo de Wikipedia es un buen lugar para comenzar a leer. Todavía hay muchas preguntas abiertas asociadas.
fuente
La entrada de Wikipedia a la que Peter se vinculó menciona algunos ejemplos importantes de problemas que tienen reducciones del caso más desfavorable al promedio, como el permanente. El problema de vector más corto (así como los problemas de red relacionados) es otro ejemplo importante, vea el artículo de Ajtai y lo que vino después (trabajos de Regev, Micciancio, Peikert, ...).
Una de las únicas observaciones generales que tenemos con respecto a los problemas con la reducción del peor de los casos al caso promedio es la siguiente (comenzada con el trabajo de Feigenbaum y Fortnow ): (al menos para las reducciones no adaptativas), es probable que estos problemas no sean completas a clases que (probablemente) no están cerradas bajo el complemento (por ejemplo, no es probable que sean NP-completas).
fuente