Actualización importante (Oct. 6, 2010): me complace decir que me dio el "azar 3SAT" problema en la OP a Allan Sly, y él vino para arriba con un simple NP-de la dureza de la prueba. He publicado la prueba a mi blog con el de Allan tipo de permiso.
Siento que estoy extraordinariamente tarde a este debate!
Respecto de Tim pregunta específica: si nos atenemos suficiente cláusulas en nuestro ejemplo, que cada 3SAT instancia (válido o no) se produce como un subformula, con alta probabilidad, entonces, ciertamente, el problema resultante será NP-duro. De hecho, bastaría con disponer de un gran conjunto de cláusulas que siempre podemos encontrar un subformula que puede servir como salida de una de las reducciones. Por otro lado, no sé de ninguna de las técnicas para la demostración de NP-dureza que se adaptan a la configuración de Tim tiene en mente, es una excelente pregunta!
Ya que yo no puedo responder a esa pregunta, permítanme hablar un rato sobre una pregunta que él no preguntar (pero que yo, y al parecer algunos de los comentaristas, que inicialmente se pensó que él hizo). Es decir, lo que se conoce acerca de la cuestión general de si son NP-completos, problemas que se pueden mostrar son NP-hard en promedio (en algunas distribución natural en instancias)?
(1) La respuesta corta es que ha sido uno de los grandes problemas sin resolver de la ciencia computacional teórica de los últimos 35 años! Si hubo un NP-completo problema que usted podría probar fue tan duro, en promedio, como lo fue en el peor de los casos, que sería un gran paso hacia la construcción de un criptosistema que fue NP-difícil de romper, que es uno el santo grial de la criptografía.
(2) Por otro lado, si usted está dispuesto a ir por encima del tipo NP-completo, sabemos que ciertas #P-complete problemas (como la Permanente a través de grandes campos finitos) tienen peor de los caso/media-caso de equivalencia. Es decir, es exactamente igual de duro para el cálculo de la permanente de un uniforme de la matriz aleatoria como para el cálculo de la permanente de cualquier matriz, y esto puede ser demostrado a través de una explícita (aleatoria) de reducción.
(3) del mismo modo, si usted está dispuesto a ir a continuación del tipo NP-completo, entonces hay criptográficos problemas, tales como el menor de celosía vector (mencionado por Runa) y logaritmo discreto, que se sabe que tienen peor de los caso/media-caso de la equivalencia. De hecho, esta propiedad está directamente relacionada con ¿por qué este tipo de problemas son útiles para la criptografía en el primer lugar! Pero, por desgracia, es también relativa a por qué no cree que ser NP-completo. Lo que me lleva a...
(4) Tenemos algunos resultados negativos, lo que sugiere que el peor de los caso/media-caso de equivalencia para un NP-completo problema requerirá de nuevas ideas si es posible en absoluto. (Harrison, aludía a estos resultados, pero que exagerado el caso un poco.) En particular, Feigenbaum y Fortnow mostraron que, si hay un NP-completos, problema que es el peor de los caso/media-caso equivalente en aleatorizado, no adaptativa reducciones, entonces el polinomio de jerarquía se derrumba. (Su resultado fue reforzada posteriormente por Bogdanov y Trevisan.) Hay análogos resultados negativos acerca de basar crytographic de ida de las funciones de los NP-completos problema: por ejemplo, Akavia, Goldreich, Goldwasser, y Moshkovitz (fe de erratas). En la actualidad, sin embargo, ninguno de estos resultados se descarta la posibilidad de un problema NP-completo, en promedio, en virtud de la mayoría de la clase general de las reducciones: a saber, randomized adaptive reducciones (donde se puede decidir con qué alimentar el oráculo basado en sus respuestas a las consultas anteriores).
(5) Todo lo que he dicho anteriormente supone implícitamente que, cuando decimos que queremos un promedio de caso de tipo NP-completo problema, que queremos decir con una distribución a través de las instancias que de manera eficiente samplable. (Por ejemplo, 3SAT con generada aleatoriamente cláusulas satisfacer esa condición, como casi cualquier otra cosa que surge de forma natural.) Si usted permite que cualquier distribución en todo, entonces hay una "trampa" para obtener el promedio de caso de NP-completitud. Este es Levin la distribución universal U, donde cada instancia de x ocurre con probabilidad proporcional a $2^{-K(x)}$, K(x), siendo el test de Kolmogorov complejidad de x. En particular, para cualquier polinomio fijo de tiempo de máquina de Turing M, el lexicográficamente-primera instancia en la que M no se tiene una descripción corta (yo sólo le dio), y por lo tanto se producen en U con gran probabilidad!
(6) Si usted está dispuesto a arreglar un polinomio en tiempo del algoritmo de M, entonces hay un hermoso resultado de Gutfreund, Shaltiel, y Ta-Shma que le da una forma eficiente-samplable de distribución de más de NP-completos problema instancias eso es duro para M, suponiendo que $NP \nsubseteq BPP$. La idea básica aquí es simple y sorprendente: la de alimentar a M su propio código como entrada, y preguntar a encontrar una instancia en la que ella misma falla! Si tiene éxito, entonces M sí actúa como su sampler de duro de los casos, mientras que si falla, entonces la instancia que sólo le dio fue el duro instancia que quería!
(7) por último, ¿qué hay de "natural" de las distribuciones, como la distribución uniforme sobre todos los 3SAT casos con n las cláusulas y m~4.3 n variables? Para aquellos que, por desgracia, en general, no tienen ningún formal de los resultados de dureza.
