Solo puede encontrar el número mínimo de puertas en una red de múltiples niveles resolviendo un entero problema de programación [o equivalentes, ver más abajo]. Este problema es NP-completo, por lo que solo es práctico para resolver hasta una docena de puertas o algo así.
Existen métodos de aproximación que no le darán el número mínimo, pero son más manejables en términos del tiempo requerido ... Estos son un gran tema en sí mismos, básicamente todo el campo de la optimización multinivel. Puede leer una descripción general [gratuita] aquí .
Para redes pequeñas de NAND (hasta 4 variables), el problema se resolvió completamente mediante enumeración exhaustiva [o métodos equivalentes]. Hay una tesis de doctorado bastante reciente de [Elizabeth], que resume los resultados antiguos y se extiende ellos. Ernst utiliza ramificación y unión, lo que mejora el método exhaustivo en la práctica, pero no asintóticamente. También señala que otros métodos de enumeración implícita, como la programación de enteros o CSP (satisfacción de restricciones, resueltos mediante SAT) se desempeñan peor en la práctica.
Obviamente ella escribió algún software para su método (llamado BESS), pero no estoy seguro si está disponible públicamente en algún lugar. El texto completo de su tesis está disponible gratuitamente en umich . Y de hecho, encontró la expresión mínima para xor de 2 entradas (su segunda, obviamente), la que se resalta a continuación:
Tambiéncomparólosresultadosexactos(paraNAND)conlosproducidosporeloptimizadorheurísticode ABC .
ABC pudo producir una red óptima para 340 de las 4,043 funciones en las que se conoce la red óptima. Para aquellas funciones en las que ABC no produjo una red óptima, fue en promedio un 36% más grande que la red óptima [.]
Hay (obviamente) algunas redes [más grandes] para las cuales BESS no terminó, pero permitió que se encontrara un límite superior (en el punto donde se abandonó la búsqueda). Para aquellos, ABC lo hizo bastante bien [bien con respecto a los límites encontrados], como se puede ver en el segundo gráfico a continuación.
