Complexity analysis of the cost-table approach to the design of multiple-valued logic circuits

摘要

We analyze the computational complexity of the cost-table approach to designing multiple-valued logic circuits that is applicable to I/sup 2/L, CCDs, current-mode CMOS, and RTDs. We show that this approach is NP-complete. An efficient algorithm is shown for finding the exact minimal realization of a given function by a given cost-table.