Take the 2-minute tour ×

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


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.

share|improve this question
out of curiosity: is this somehow related to VHDL? –  Scoregraphic Aug 4 '10 at 14:05
For a given circuit, it might not be possible at all (i.e. x and not x) to produce both output states. –  John with waffle Aug 4 '10 at 14:09
Are the gates always 3-input AND gates, or could they be any types of gates? –  mbeckish Aug 4 '10 at 14:58

2 Answers 2

up vote 13 down vote accepted

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:

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)
share|improve this answer
Well if we try the first input vector, then we've solved half of the problem already :-) –  Nordic Mainframe Aug 4 '10 at 14:15
@Luter Blissett: +1 Good point! I had better mention that in the answer. –  Mark Byers Aug 4 '10 at 14:23

This is solved with the Quine McCluskey algorithm. There are also some JavaScripts and Tools which may solve your problem.

share|improve this answer
<en.wikipedia.org/wiki/Quine–McCluskey_algorithm> –  Paul D. Waite Aug 4 '10 at 14:56

Your Answer


