Function Decomposition

The problem:

Given a set of base functions, a composite function is built and the number of functions used is returned and a set of constraints that the generated function fulfills is returned. Find a function with equal or lesser complexity that also fulfills the constraints.

Base functions can take any number of arguments and returns one value. All values are of the same type.

Example

Base Functions ADD(a, b), MUL(a, b), GT(a, b)

where GT returns 1 if a>b and 0 otherwise.

But what if base functions include binary operations (which are non-linear).

Proof Of Impossibility

If this were generally possible, it would be possible to reverse engineer a crypto hash.

Possible Constraints

Base Inversion

Require that for each base function an inverse function is also supplied. The inverse is not (necessarily) part of the set.

 F(a,b) = c → F'1(a,c) = b and F'2(c,b) = a

However, GT doesn't have an inverse.

It may work to only require an inverse over a set, which can be filled for GT.

Possible Sub-problems

Solve for Constants

From the original problem, let's say I return the function tree with no values filled in. Each argument is either going to be a constant or a top level argument. How to solve the values?

Something like back propagation may work here. proportionally change each value based on how much it's contributing to the error. This may require some sort of derivative. And it won't work if the out put of a function is chaotic.

It may also help to have linear approximations of non-linear functions. For instance GT could be approximated by a sigmoid function which is progressively tuned steeper and steeper.