Redundancia y estructura de los problemas computacionales

Question

Está muy extendida la creencia de que algunos problemas computacionales como el isomorfismo de grafos no pueden ser NP-completos porque no poseen suficiente estructura o redundancia para ser computacionalmente duros (NP-hard). Estoy interesado en las diferentes nociones formales para la estructura de los problemas computacionales y las medidas de redundancia.

¿Cuáles son los principales resultados conocidos sobre estas nociones formales para los problemas computacionales? Estaría muy bien un estudio reciente de dichas nociones.

Se publicó en TCS stackexchange sin ninguna respuesta.

Answer 1

En mi experiencia, cuando un teórico de la complejidad (o de la computabilidad) habla de la "estructura" de una clase de lenguajes, casi siempre está utilizando una noción informal que, si bien puede ser apreciada a nivel intuitivo por otros que han estudiado la clase, actualmente está más allá de la capacidad de nadie para formalizarla.

La creencia generalizada de que (digamos) $GI \ne NP$ viene tanto de los pocos resultados que tenemos (por ejemplo, que $GI$ está en la jerarquía baja de $NP$ ) que tendría consecuencias sorprendentes o contradeciría otras creencias muy extendidas, como ocurre con la idea algo más vaga de que "no hay suficiente estructura" (¿o "demasiada estructura"?) en $GI$ .

La "redundancia" puede ser una noción más fácil de precisar formalmente, utilizando, por ejemplo, la complejidad de Kolmogorov. Pero en cierto sentido, el estudio de los límites inferiores es Dada la dificultad de demostrar los límites inferiores, espero que la formalización de la noción de redundancia sea igualmente difícil.