Notes on "Complexity of the lookup-table minimization problem for FPGA technology mapping"
Shujian Zhang, D. Michael Miller, Jon C. Muzio · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1996
For the original article see IEEE Trans. Computer-Aided Design, vol. 13, no. 11, p. 1319-32 (1994). In this paper, we prove that 3-RLMP and 4-RLMP, proposed by Farrahi and Sarrafzadeh in the aforementioned paper, are NP-complete.