¿Puede un problema NP-hard ser polinomial en promedio?

11

Me pregunto si hay duros que son "polinomiales" en el caso promedio. ¿Creo que hay dos formas de interpretar esto?NP

  • Si , ¿puede haber un algoritmo que resuelva un problema duro con tiempo de ejecución amortizado (caso promedio) de para una constante ?N P O ( n k ) kP≠NPNPO(nk)k
  • ¿Hay algún problema que sea duro que también esté en , o incluso ?B P P P PNPBPPPP

¿Alguien puede responder o proporcionar una referencia para responder cualquiera de estas preguntas?

complexity-theory reference-request np-complete probabilistic-algorithms amortized-analysis jmite
fuente
55
Esta pregunta apareció en la teoría CS hace un tiempo, aquí está el enlace cstheory.stackexchange.com/questions/496/…
lPlant
Ah, excelente! ¿Debo cerrar / eliminar esta pregunta entonces?
jmite
2
@jmite: Esto puede ser útil para mantener por aquí, así que ¿tal vez publicar una respuesta rápida (auto) con una referencia aquí?
Raphael
1
Solo me gustaría señalar que amortizado no es lo mismo que el tiempo de ejecución promedio de los casos.
cabeza de jardín
Si un problema NP-duro está en BPP, significa que NP está en BPP, lo que significa que la jerarquía polinómica se colapsa, un resultado que se considera poco probable. Por otro lado, no creo que no se considere muy improbable que PP contenga NP ya que . (Es posible que desee preguntar sobre evidencia a favor y en contra de NP en PP sobre Ciencias de la Computación Teóricas ).PH⊆PPP
Kaveh

Respuestas:

5

Parece que la pregunta ha sido respondida en CSTheory.SE .

Resumen: es, de hecho posible.

Por ejemplo, el problema de Max 2-CSP es NP difícil con un algoritmo de tiempo esperado .O(n)

Esto tiene sentido, supongo. A veces, solo se necesita un pequeño subconjunto de instancias para hacer un problema duro, como SAT vs 3SAT. Pero puede expandir el problema, y ​​siempre que contenga las instancias difíciles, será NP-difícil, pero aumentará la probabilidad de éxito con un algoritmo rápido.NP

jmite
fuente