Actualización importante (6 de octubre de 2010): Me complace decir que le di el problema de "3SAT al azar" en el OP a Allan Sly, y él vino con una simple prueba de dureza NP. He he publicado la prueba en mi blog con el amable permiso de Allan.
Siento llegar extraordinariamente tarde a esta discusión.
En cuanto a la pregunta concreta de Tim: si metemos suficientes cláusulas en nuestra instancia que cada Si una instancia de 3SAT (satisfacible o no) ocurre como una subfórmula con alta probabilidad, entonces ciertamente el problema resultante será NP-duro. De hecho, bastaría con tener un conjunto de cláusulas lo suficientemente grande como para poder encontrar siempre una subfórmula que pueda servir como salida de una de las reducciones estándar. Por otro lado, no conozco ninguna técnica para demostrar la dureza NP que se adapte al escenario que Tim tiene en mente, ¡es una pregunta estupenda!
Ya que no puedo responder a la pregunta que hizo, permítanme hablar un rato de una pregunta que no hizo (pero que yo, y al parecer algunos de los comentaristas, pensamos inicialmente que sí). A saber, lo que se sabe sobre la cuestión general de si hay problemas NP-completos que uno puede demostrar que son NP-difícil en promedio (bajo alguna distribución natural sobre las instancias)?
(1) La respuesta corta es que ha sido uno de los grandes problemas sin resolver de la informática teórica durante los últimos 35 años. Si existiera un problema NP-completo que se pudiera demostrar que es tan difícil en promedio como en el peor de los casos, eso sería un gran paso hacia la construcción de un criptosistema que era difícil de romper NP, que es uno de los santos griales de la criptografía.
(2) Por otro lado, si está dispuesto a ir más allá de NP-completo, sabemos que ciertos #P-completo problemas (como el Permanente sobre campos finitos grandes) tienen equivalencia caso peor/caso medio . Es decir, es exactamente tan difícil calcular la permanente de una matriz aleatoria uniforme como lo es calcular la permanente de cualquier matriz, y esto se puede demostrar mediante una reducción explícita (aleatoria).
(3) Asimismo, si estás dispuesto a ir debajo de NP-completo, entonces hay problemas criptográficos, como el vector de red más corto (mencionado por Rune) y el logaritmo discreto, que se sabe que tienen equivalencia en el peor caso/caso medio. De hecho, esta propiedad está directamente relacionada con la razón por la que estos problemas son útil ¡para la criptografía en primer lugar! Pero, por desgracia, también está relacionado con la razón por la que se cree que no son NP-completas. Lo que me lleva a...
(4) Tenemos algunos resultados negativos, que sugieren que la equivalencia caso peor/caso medio para un problema NP-completo requerirá ideas muy nuevas si es que es posible. (Harrison aludía a estos resultados, pero exageró un poco el caso). En particular, Feigenbaum y Fortnow demostró que, si hay un problema NP-completo que es equivalente en el peor de los casos o en el caso medio bajo reducciones aleatorias y no adaptativas entonces la jerarquía polinómica se colapsa. (Su resultado fue reforzado posteriormente por Bogdanov y Trevisan .) Existen resultados negativos análogos sobre la base de las funciones criptográficas unidireccionales en un problema NP-completo: por ejemplo, Akavia, Goldreich, Goldwasser y Moshkovitz ( errata ). Sin embargo, actualmente ninguno de estos resultados descarta la posibilidad de que un problema sea NP-completo en promedio bajo el tipo más general de reducciones: es decir, aleatorizado adaptativo (donde se puede decidir qué alimentar al oráculo en función de sus respuestas a las consultas anteriores).
(5) Todo lo que he dicho anteriormente supone implícitamente que, cuando decimos que queremos un problema NP-completo de caso medio, queremos decir con una distribución sobre las instancias que es muestreable de forma eficiente . (Por ejemplo, 3SAT con cláusulas generadas aleatoriamente satisfaría esa condición, al igual que casi cualquier otra cosa que surja de forma natural). Si se permite cualquier entonces hay una forma "engañosa" de obtener la completitud NP de caso medio. Se trata de La distribución universal de Levin U, donde cada instancia x ocurre con probabilidad proporcional a $2^{-K(x)}$ K(x) es la complejidad de Kolmogorov de x. En particular, para cualquier máquina de Turing de tiempo polinómico M, la primera instancia lexicográfica en la que falla M tendrá una descripción corta (la acabo de dar), y por lo tanto ocurrirá en U con una gran probabilidad.
(6) Si estás dispuesto a fijar un algoritmo de tiempo polinómico M, entonces hay un hermoso resultado de Gutfreund, Shaltiel y Ta-Shma que da una distribución eficientemente ampliable sobre instancias de problemas NP-completos que es difícil para M , suponiendo que $NP \nsubseteq BPP$ . La idea básica es simple y sorprendente: le das a M su propio código como entrada y le pides que te encuentre una instancia en la que él mismo falle. Si tiene éxito, entonces M actúa como su muestreador de instancias difíciles, mientras que si falla, entonces la instancia que le acabas de dar era la instancia difícil que querías.
(7) Por último, ¿qué pasa con las distribuciones "naturales", como la distribución uniforme sobre todas las instancias de 3SAT con n cláusulas y m~4,3n variables? Para estos casos, por desgracia, generalmente no tenemos cualquier resultados de dureza formal.
