Este es un ejemplo del tipo de cosas a las que me refiero. Consideremos una instancia aleatoria de 3-SAT, en la que se eligen suficientes cláusulas para que la fórmula sea casi seguramente insatisfactible, pero no demasiadas más que eso. Así que ahora tienes una pequeña fórmula aleatoria que es insatisfactible.
Dada esa fórmula, se puede preguntar, para cualquier subconjunto de sus cláusulas, si ese subconjunto da una fórmula satisfactoria. Este es un problema aleatorio (porque depende de la colección aleatoria original de cláusulas) en NP. También parece que debería ser bastante difícil. Pero demostrar que suele ser NP-completo también parece ser difícil, porque no se tiene la libertad habitual de simulación.
Así que mi pregunta es si se conoce algún resultado que diga que algún problema aleatorio es NP-completo. (Se pueden inventar ejemplos artificiales tontos como tener una parte aleatoria que no tenga efecto en el problema - de ahí la palabra "interesante" en la pregunta).
