Geek Answers Handbook

An interesting problem with the algorithm

I have an interesting problem with the algorithm. The problem lies in the method of modeling electronic structures.

Say, for example, I have a structure containing some gates. let's say 3-input logic element I. There are 8 possible inputs i.e.

000 001 ... 111

From these 8 inputs, if I feed only two inputs (000) and (111) , I get both possible outputs ie 0 and 1 .

So, the minimum set of input vectors that outputs the states "0" and "1", {000, 111} at the output.

The task is given a construction, some layout of the gates, gives an algorithm for finding the minimum set of input vectors, which produces as states (i.e. 0 and 1) at the final output.

+6
language-agnostic algorithm
source share
2 answers

Your problem is equivalent to solving the boolean problemability problem. Therefore, it is NP-complete.

To get one of the inputs, you can select an arbitrary input and see if it gives 0 or 1. To find an input that gives another output, you need a SAT solver.

Wikipedia offers several algorithms that can be used:

If you do not want to implement it, there are tools that are ready to use SAT solvers:

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

This is solved using the Quine McCluskey algorithm. There are also JavaScripts and tools that can solve your problem.

+5
source share

More articles:


All Articles