Modelling of minimal NOR-circuit problem with CP

Question

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."

Source : https://www.cs.upc.edu/~erodri/webpage/cps/projects/Q2-16-17/proj.pdf

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 ?

• gnasher729: Fan-out of 1 and not allowing 1 as input seem unrealistic. Fan-out of 1 is of course easily overcome by duplicating nor gates, and 1 as input is possible anywhere except the highest level.
• D.W.: It appears you are quoting from some external source. Please credit the original source of all copied or quoted material in your question.

Answer 1

This is a logic synthesis problem. Specifically, without the "fan-out of 1" limitation, this looks like the circuit minimization problem. Circuit minimization is $\Sigma_2^P$-complete, so you should not expect any efficient algorithm for it. There are many algorithms in the literature that you can explore, including Karnaugh Maps, Quine-McCluskey, Espresso, and others. I wouldn't consider constraint programming the obvious first way to approach this problem.

If you have a requirement to use constraint programming for some homework exercise, well, you should do your own exercise, but here is a hint: you should be able to tell whether there exists a circuit of depth $d$ and width $w$ by building a $d \times w$ grid of NOR gates, then using decision variables to represent which edges are used to connect these gates. How could you use that to solve the original problem?

Limiting fan-out to 1 seems unrealistic, as gnasher729 explains.

• Shinra_SGr: I think I got the main idea. I should start with trying to solve the problem : is there a Nor-circuit with depth d that satisfies the truth table ?
• Shinra_SGr: I can even find the circuit with the minimal number of gates. I start with d = 1 , if a find an answer I'm done, if not I try to solve the same problem with d= 2 and so on ... To solve one of those problems, I can use what you suggest with the grid (not sure about how to fix w though, maybe n+1, with n the number of inputs). Of course I will have to add constraints fot the truth table and how to connect gates. I will also need some others variables but it seems doable that way.