Inferring simplest method to convert bit array 1 to bit array 2
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 &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.

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 (preprint)


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