Interesting algorithm problem

Question

I have an interesting algorithm problem here. The problem is in a way related to simulation of electronic designs.

Say for example, I have a structure containing some gates. say a 3-input AND gate. There are 8 possible inputs i.e

000
001
...
111

Out of these 8 inputs, if I only feed in two inputs (000) and (111), I get both the possible outputs i.e 0 and 1.

So The minimal set of input vectors that produces both the states '0' and '1' on the output are {000, 111}.

The problem is given a design, some arrangement of gates, give an algorithm to find the minimal set of input vectors that produces both the states (i.e 0 and 1) on the final output.

Answer 1

Your problem is equivalent to solving the boolean satisfiability problem. It is therefore NP-complete.

To get one of the inputs you can choose an arbitrary input and see if that gives either 0 or 1. To find an input that gives the other output you need a SAT solver.

Wikipedia suggests some algorithms that can be used:

• DPLL algorithm
• Chaff algorithm
• GRASP
• WalkSAT
• etc...

If you don't want to implement it, there are tools that are ready-to use SAT solvers:

• CVC3 (open-source LGPL)
• Yices (free for non-commercial use)