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.
雑誌名
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
巻
E94D
号
1
ページ
35 - 41
発行年
2011
出版者
IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
On Two Problems of Nano-PLA Design
IEICETIS_94_1_35_41
(1.01MB)
