¿Es fácil detectar instancias fáciles de problemas NP-hard?

Mi pregunta es la siguiente. Suponga que es un problema NP-hard. Dada una instancia arbitraria de y suponiendo que un adversario sabe que esta instancia es fácil de resolver, ¿es posible encontrar un algoritmo determinista de tiempo polinómico para resolver esta instancia particular ?$\Pi$$I$$\Pi$$I$

Por ejemplo: supongamos que es COLORACIÓN GRÁFICA. El adversario te da una gráfica con vértices.$\Pi$$G$$n$

1. El adversario sabe que está completo pero tú no. ¿Puedes encontrar un algoritmo de tiempo polinómico que diga "Este gráfico es coloreable con colores"?$G$$\Delta +1$
2. El adversario sabe que tiene alguna propiedad pero usted no. ¿Puedes encontrar un algoritmo de tiempo polinómico que diga "Este gráfico es coloreable con colores"?$G$$P$$b$
3. ...

El problema no está realmente bien planteado. Para cualquier caso particular, no hay una única solución, decir . En consecuencia, podemos imaginar un algoritmo que tiene la respuesta hardcoded en: no importa qué datos ofrecidos por usted, lo único que hace es simplemente imprimir . Esta respuesta se cuenta como un algoritmo de tiempo polinomial determinista que resuelve este caso particular .$S$$S$$S$$I$

Por lo tanto, la respuesta a su pregunta es "Sí", pero por razones poco interesantes. Es posible que necesite pensar más sobre cómo formular su pregunta para que coincida con lo que realmente quiere saber.

La parte final de su pregunta es en realidad un poco diferente. No pregunta acerca de una sola instancia . Más bien, pregunta sobre un caso especial del problema, es decir, una familia infinita de instancias que es un subconjunto adecuado de todas las instancias posibles para . En ese caso, la respuesta es "depende"; algunos casos especiales pueden permanecer NP-hard, y otros pueden estar en P.$I$$\Pi$

Finalmente, no sé lo que significa decir "El adversario sabe X pero tú no". Soy libre de escribir un algoritmo que asuma que X es verdadero y solo funciona cuando X es verdadero. El "conocimiento" es algo divertido y no está bien modelado por el tipo de herramientas de las que parece estar hablando; La teoría de la complejidad tiene más que ver con la "existencia" que con el "conocimiento".

En cierto sentido, la respuesta a su pregunta es afirmativa, debido al algoritmo de búsqueda universal de Levin. Considere la coloración del gráfico de concreción y una clase particular de instancias fáciles. Como testigo de que esta clase es fácil, tiene un algoritmo que, dado un gráfico en esta clase, produce (en tiempo polinómico) una coloración legal junto con una prueba de tamaño polinomial de que la coloración es óptima.

El algoritmo de búsqueda universal de Levin ejecuta todos los algoritmos de tiempo polinomiales en su instancia (esto se logra probando todos los límites de tiempo polinómicos posibles para cada algoritmo), verificando si proporcionan una coloración legal junto con una prueba de optimización. En cualquier clase de instancias fáciles, este algoritmo se ejecuta en tiempo polinómico. Lamentablemente, las constantes serán enormes, por lo que este algoritmo no es práctico.