<p>Multi-level logic synthesis has been a research topic for decades. To apply a sequence of local transforms for circuit improvement is a strategy pursued by the <a href="http://www.eecs.berkeley.edu/%7Ealanmi/abc/" rel="nofollow noreferrer">Berkeley ABC system</a>.</p>
<p>A related paper is <a href="https://people.eecs.berkeley.edu/%7Ealanmi/publications/2007/tech07_imfs.pdf" rel="nofollow noreferrer">SAT-Based Logic Optimization and Resynthesis</a>.
A recent publication is <a href="https://arxiv.org/pdf/2105.01755" rel="nofollow noreferrer">Reinforcement Learning for Scalable Logic
Optimization with Graph Neural Networks</a>.</p>
<p>Usually, the local transforms start out with a correct circuit and try to improve it without touching its correctness. To transform some arbitrary circuit into a correct one does not look promising to me.</p>
<p>The truth-table of a circuit with <code>n</code> inputs has <code>2^n</code> rows. To check the correctness, the optimizer has to check all <code>2^n</code> values. The number of matches (= the fitness measure) is between <code>0</code> and <code>2^n</code>. There are typically many possible ways to transform the circuits. Therefore, the tree of alternatives quickly explodes for more than a handful inputs.</p>
<p>A possible search approach would be to decompose the function <code>F</code> to be implemented into two simpler functions <code>F1</code> and <code>F2</code> such that</p>
<pre><code>F(a, b, ....) = NOR(F1(a, b, ....), F2(a, b, ....))
</code></pre>
<p>This split can be optimized to minimize the complexity of the sub-functions <code>F1</code> and <code>F2</code>.</p>
<p>The approach is recursive. <code>F1</code> and <code>F2</code> are decomposed into sub-functions. The recursion ends, if a function just represents a constant or a single input variable.</p>
<p>The resulting circuit is a tree of two-input <code>NOR</code> gates. It might be possible to re-use already synthesized sub-functions or allow <code>NOR</code> gates with varying number of inputs (<code>INV</code>, <code>NOR2</code>, <code>NOR3</code>, ...).</p>
what would be the most efficient algorithm for logic circuit synthesis if the only known knowledge about the problem is the fitness function?
<p>I'm developing a program that tries to build logic circuit from NOR gates given some fitness function (logic_circuit =&gt; fitness_value).</p>
<p>currently I'm using some kind of simulated annealing(make N random mutations to logic circuit graph and calculate fitness of new solution if fitness high enough than accept as current solution)</p>
<p>is there more efficient algorithms for this kind of problem?</p>
<p><a href="https://i.stack.imgur.com/3qkBa.png" rel="nofollow noreferrer">Here is an example of generated AND gate with 4 inputs</a>(0-1 on edge means, the edge goes from 0 output go to the 1th(right) input of another gate)</p>
<p><a href="https://i.stack.imgur.com/s8I0u.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/s8I0u.png" alt="enter image description here" /></a></p>