I'm currently working on a Constraint Programming problem which I find difficult to model.
Here 's the definition of the problem :
" Given a specification of a Boolean function f(x1, ..., xn) in the form of a truth table, to find a NOR-circuit (meaning only NOR gates) satisfying the specification that minimizes depth (and, in case of a tie in depth, with minimum size). In order to simplify the problem, several assumptions are made:
• Only NOR gates with 2 inputs and 1 output can be used: more general NOR gates with more inputs are not allowed (i.e., the fan-in of NOR gates is always 2).
• The output of a NOR gate can only be the input of a single gate: outputs cannot be reused as inputs of more than one gate (i.e., the fan-out of NOR gates is always 1).
• In addition to the input signals of the Boolean function to be implemented, constant 0 signals can also be used as inputs of NOR gates. Constant 0 signals as well as input signals can be used as many times as needed as inputs of NOR gates. On the other hand, the circuit does not need to use all input signals. Similarly, the constant 0 signal does not have to be used if it is not needed."
Since this is the first time that I'm confronted to this kind of problem, I'm having difficulties finding "good" decision variables. Maybe I'm missing something trivial ...
Do you have any idea/hint on how to model this problem ?