CODEWITHSUNDEEP
algorithmlanguage-agnostic
sud03r
sud03r

Reputation: 19769

Interesting algorithm problem

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.

Upvotes: 6

Views: 589

Answers (2)

codymanix
codymanix

Reputation: 29490

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

Upvotes: 5

Mark Byers
Mark Byers

Reputation: 838716

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)

Upvotes: 13

Related Questions