¿Qué se sabe sobre la complejidad de los problemas NP-hard en los gráficos Cayley?
Suponga que la gráfica se da explícitamente como la tabla de multiplicación del grupo y la lista de generadores. Entonces la longitud de entrada es el tamaño de la gráfica. ¿Podemos resolver problemas de NP completo en tales gráficos (camarilla máxima / corte máximo) en tiempo polinómico?
¿Qué pasa con algunos casos especiales de grupos? Por ejemplo, (también conocido como gráficos circulantes) o Z log ( n ) 2 . Es decir, la entrada al problema es el conjunto de generadores (y 1 n para representar el tamaño del gráfico).
fuente