El factoring está en NP intersect coNP, pero se sabe que el isomorfismo gráfico solo está en NP. No hemos demostrado que no haya algún algoritmo que decida GI asintóticamente más rápido de lo que cualquier algoritmo puede factorizar, pero el estado actual del conocimiento sugiere que la factorización es más fácil.
Digamos que se pregunta si 323 tiene algún factor primo menor que 16. Si le digo que 17 x 19 = 323, entonces sabe que la respuesta a su pregunta es “no”. Esto se debe a que está explotando una estructura matemática profunda, a saber, el Teorema fundamental de la aritmética que le dice que 323 debe tener exactamente una factorización prima.
Ahora supongamos que desea saber si (G1, G2) son gráficos isomorfos, y traigo un gráfico diferente G3 y le muestro que G1 es isomorfo a G3. Eso no te da ninguna idea sobre tu pregunta original. La razón por la cual GI parece más difícil es que no sabemos qué evidencia podría brindarle que alguna vez lo haga darse cuenta de esos momentos en que la respuesta a su pregunta es “no”, es decir, no creemos que GI esté en coNP.
- ¿Cuánto conocimiento sobre circuito (o VLSI) se necesita para investigar en el campo de la arquitectura de computadoras?
- En la investigación de CS, ¿cuál es la relación de pensamiento a implementación?
- ¿Cuáles son algunos problemas interesantes de PSPACE-complete?
- ¿Cuál es el patrimonio neto de ACM?
- ¿Cuáles son los problemas en la educación en informática?
