How to find minimum number of k-input LUTs needed to express a n variable boolean function? An k-input LUT (look up table) takes in atmost k-inputs and gives 1 output (which is a function of the k inputs). I need to devise an algorithm to find the minimum number of k-input LUT's required to express a n variable boolean function.

For example : - n=8 and k=4 8 input variables are a0,a1...a7

1) f1(a0,a1,..a7)= a0*a1 +a3*a4 + a5*a7 + a6*a8 Requires 3 LUTs : LUT1 :a0*a1 + a3*a4 =x1 LUT2 :a5*a7 + a6*a8 =x2 LUT3 : x1+x2

2) f2(a0,a1,..a7)= a0*a1 +a3*a4 + a5*a7 + a6 Requires 2 LUTs : LUT1: a0*a1 +a3*a4 =x1 LUT2: x1+a5*a7+a6

NOTE: I want to solve this for the particular case of n=8 and k=4. Though, I would like to extend it to other cases like (n,k)= (8,2).
The following decision version of your problem is NP-complete:


  Given a formula $f$, an integer $k$, and an integer $s$ (encoded in unary), determine whether $f$ can be represented using at most $s$ many $k$-input LUT's.


Indeed, you can easily solve SAT by asking whether the instance of SAT can be represented using at most one 0-input LUT. If you disallow $k=0$, you need to work a bit harder: a formula $\phi$ is satisfiable iff $\phi \oplus x$ (where $x$ is a fresh variable) can be represented using at most one 1-input LUT.