<p>There is clearly an algorithm, since the finite search space can be explored using brute force.  This takes a long time...</p>

<p>Instead of considering $f \colon \{0,1\}^n \to \{0,1\}^n$, one can look at the Boolean function $f' \colon \{0,1\}^{2n} \to \{0,1\}$ defined by $f'(xy) = 1$ iff $f(x) = y$.</p>

<p>No polynomial-time algorithm is known to find a minimum-size circuit for a Boolean function, which is known as the Minimum Circuit Size Problem (MCSP).  However, MCSP is in NP.</p>

<p>If MCSP were in P, then one could factor in average time $2^{n^\epsilon}$ time (for any $\epsilon &gt; 0$) numbers that are products of two primes, each of which is congruent to 3 modulo 4.  These numbers are quite hard to factor in practice, so this would be quite surprising.</p>

<p>On the other hand, if the MCSP is NP-complete, then this would imply strong circuit lower bounds for the class E = DTIME($2^{O(n)}$), which we don't currently know how to do.</p>

<ul>
<li>Valentine Kabanets and Jin-Yi Cai, <em>Circuit Minimization Problem</em>, STOC 2000, 73–79. doi:<a href="http://dx.doi.org/10.1145/335305.335314">10.1145/335305.335314</a> (<a href="http://eccc.uni-trier.de/report/1999/045/">preprint</a>)</li>
</ul>

<p>So no polynomial-time algorithms seem likely for your problem, unless you can exploit special features of the functions you are interested in.</p>

CC BY-SA 3.0
2013-05-14T17:25:06.583Z
2013-05-14T17:25:06.583Z
András Salamon
<p>Consider the set of all bit arrays of length n. Now consider the set of all 1-to-1 functions that map from this set to this set.</p>

<p>Now select a single function out of the latter set. Is there any algorithm to find a "minimal" method of implementing this function? Assume that we only have access to fundamental bit array operators such as AND OR XOR NOT and left and right bitshifts.</p>

<p>In case you're wondering, the reason I want this is because I'm writing an algorithm to convert from z-curve ordering of bits to hilbert-curve ordering of bits. My current method is to make a lookup table, but I bet there's a better option.</p>

<p>As a simple example, let's say I have a truth table that looks like this:</p>

<pre><code>00 -&gt; 10
01 -&gt; 01
10 -&gt; 00
11 -&gt; 11
</code></pre>

<p>Then I should be able to infer that, given an input bit string <code>input</code>, the output bit string <code>output</code> is (in java syntax)</p>

<pre><code>output = ((~input) &lt;&lt; 1) ^ input
</code></pre>

<p><em>Here's the proof in this case:</em></p>

<pre><code>00 -&gt; 11 -&gt; 10 -&gt; 10
01 -&gt; 10 -&gt; 00 -&gt; 01
10 -&gt; 01 -&gt; 10 -&gt; 00
11 -&gt; 00 -&gt; 00 -&gt; 11
</code></pre>

<boolean-functions>
Inferring simplest method to convert bit array 1 to bit array 2
John Berryman
# Inferring simplest method to convert bit array 1 to bit array 2

(Asked by: username_0 on 2013-05-14)

Consider the set of all bit arrays of length n. Now consider the set of all 1-to-1 functions that map from this set to this set.
Now select a single function out of the latter set. Is there any algorithm to find a "minimal" method of implementing this function? Assume that we only have access to fundamental bit array operators such as AND OR XOR NOT and left and right bitshifts.
In case you're wondering, the reason I want this is because I'm writing an algorithm to convert from z-curve ordering of bits to hilbert-curve ordering of bits. My current method is to make a lookup table, but I bet there's a better option.
As a simple example, let's say I have a truth table that looks like this:
00 -> 10
01 -> 01
10 -> 00
11 -> 11

Then I should be able to infer that, given an input bit string input, the output bit string output is (in java syntax)
output = ((~input) << 1) ^ input

Here's the proof in this case:
00 -> 11 -> 10 -> 10
01 -> 10 -> 00 -> 01
10 -> 01 -> 10 -> 00
11 -> 00 -> 00 -> 11

**Tags:** boolean-functions


---

## 1 answers

### Answer by username_1 on 2013-05-14. Score: 6 | Accepted answer

There is clearly an algorithm, since the finite search space can be explored using brute force. This takes a long time...

Instead of considering $f \colon \{0,1\}^n \to \{0,1\}^n$, one can look at the Boolean function $f' \colon \{0,1\}^{2n} \to \{0,1\}$ defined by $f'(xy) = 1$ iff $f(x) = y$.

No polynomial-time algorithm is known to find a minimum-size circuit for a Boolean function, which is known as the Minimum Circuit Size Problem (MCSP). However, MCSP is in NP.

If MCSP were in P, then one could factor in average time $2^{n^\epsilon}$ time (for any $\epsilon > 0$) numbers that are products of two primes, each of which is congruent to 3 modulo 4. These numbers are quite hard to factor in practice, so this would be quite surprising.

On the other hand, if the MCSP is NP-complete, then this would imply strong circuit lower bounds for the class E = DTIME($2^{O(n)}$), which we don't currently know how to do.

* Valentine Kabanets and Jin-Yi Cai, *Circuit Minimization Problem*, STOC 2000, 73–79. doi:[10.1145/335305.335314](http://dx.doi.org/10.1145/335305.335314) ([preprint](http://eccc.uni-trier.de/report/1999/045/))

So no polynomial-time algorithms seem likely for your problem, unless you can exploit special features of the functions you are interested in.


---

