Entiendo que el problema de hacer coincidir dos listas de red podría reducirse al problema de isomorfismo del gráfico, que es NP-intermedio. Aparte de eso, ¿cuáles son los resultados de complejidad de algunos de los algoritmos de coincidencia de lista de redes utilizados actualmente?
TL; DR: El OP preguntó si la complejidad computacional de las listas de red coincidentes es diferente de la de otros tipos de gráficos. No es porque los netlists son aún Gráficos completos de GI .
La complejidad computacional aún es GI si agrega la restricción a las listas de red, porque las listas de redes experimentan los mismos peores escenarios que otros tipos de gráficos y la complejidad computacional solo se ve en el comportamiento del peor de los casos.
La única cosa real que tiene todo tipo de listas de redes en común es que están fuertemente etiquetadas.
Dentro del conjunto de todas las listas de redes, por supuesto, hay casos que son más fáciles y casos más difíciles. En general, el problema es más fácil si tiene un gráfico con muchas etiquetas diferentes. Es decir. una lista de redes de transistores donde solo tienes n-tipos y p-tipos es más difícil que una lista de redes donde tienes un número mayor de tipos de células, que a su vez es más difícil que una lista de redes para una arquitectura FPGA con N -input LUTs con \ $ 2 ^ {2 ^ N} \ $ configuraciones de LUT diferentes.
Al observar el problema del isomorfismo del subgrafo (es decir, intentar encontrar y extraer un subcircuito determinado), puede dar un máximo de. Polinomio para cada sub circuito dado. Esto es muy intuitivo: si te doy un circuito específico y te pido que escribas un código que busque este circuito, simplemente podrías codificar el patrón iterando sobre todos los candidatos para node_1 , cada candidato cuando sea elegido reduce el número posible de candidatos. para node_2 , y así sucesivamente. En el peor de los casos, esto creará K bucles en cascada para un patrón de K celdas, lo que dará como resultado una complejidad de \ $ O (N ^ K) \ $ para encontrar el circuito en una gráfica de N nodos. (Cada circuito de patrón puede permitir diferentes optimizaciones que permiten reducir la complejidad).
Como nota al margen: los algoritmos que usan una matriz de vecindario generalmente usan la siguiente codificación para el circuito: hay un nodo para cada celda y un nodo para cada red. Por lo tanto, una conexión entre dos celdas se codifica como dos bordes en el gráfico: uno de cell_1 a net_1 y uno de net_1 a cell_2 . (También he visto codificaciones que crean nodos intermedios para cada puerto de celda, pero en la mayoría de los casos, la información sobre los puertos de celda se almacena en etiquetas de borde). Esto asegurará que incluso para redes con gran fan-out (como señales de reinicio, por ejemplo) la matriz de vecindad permanece muy dispersa (número de ceros no lineales al número de celdas y redes, en lugar de la complejidad cuadrática para la codificación ingenua).
Un buen algoritmo que puede extenderse fácilmente a las necesidades de un dominio de problema específico es el Ullmann subgraph isomorphism algorithm . Ya es bastante antiguo y no es el algoritmo más eficiente, pero creo que es un algoritmo muy claro y aprenderlo ayuda a comprender mejor el problema que resuelve.