On Two Problems of Nano-PLA Design
Anish Man Singh Shrestha, Asahi Takaoka, Satoshi Tayu, Shuichi Ueno · IEICE Transactions on Information and Systems · 2011
The logic mapping problem and the problem of finding a largest sub-crossbar with no defects in a nano-crossbar with nonprogrammable-crosspoint defects and disconnected-wire defects are known to be NP-hard. This paper shows that for nano-crossbars with only disconnected-wire defects, the former remains NP-hard, while the latter can be solved in polynomial time.