How to go about finding the most "complex" function?
Pick one at random. 

If it is random, then there is no way to compress the representation. You have to store the entire truth table.

http://en.wikipedia.org/wiki/Kolmogorov_complexity