How might one measure the difficulty of formulae?

[Vladimir Batagelj]

PS. In the proposed measure

  complexity =
  average depth of tree leaves   X  average degree of internal nodes

the degree is out-degree (number of sons of a node).

For example

   (-b+sqrt(b^2-4ac))/(2a)
                                                      out-degrees of
    depth                                             internal nodes

     0                         /                             2
                           /       \
     1                    +         *                    2       2
                        /   \     /   \
     2                 -   sqrt  2     a              1     1
                      /       \
     3               b         -                               2
                            /     \
     4                    ^2       *                        1     3
                          /      / | \
     5                   b      4  a  c

Therefore
    average depth  = (3+5+5+5+5+2+2)/7 = 27/7
    average degree = (2+2+2+1+1+2+1+3)/8 = 14/8 = 7/4
    complexity     = 27/7 X 7/4 = 27/4 = 6.75

For an expression consisting of single variable or constant we set
complexity = 1.

f(g(h(x)))

    f
    |
    g
    |
    h
    |
    x        complexity = 3 X 1 = 3

f(x,y,z)

       f
     / | \
    x  y  z     complexity = 1 X 3 = 3

There are two possibilities how to treat associative cases such as
   a + b + c + d
The first option is

                 +
           /   /   \   \
          a   b     c   d      complexity = 1 X 4 = 4

and the second

              +
            /   \
           a     +
               /   \
              b     +
                  /   \
                 c     d       complexity = 9/4 X 2 = 4.5

If the names of variables and functions are of different length
the measure can be extended by the additional length term. For
example:

  complexity =
  average depth of tree leaves   X
  average degree of internal nodes  X
  sqrt(average length of the names)

Note also that
  leaves = variables and constants
  internal nodes = operations and functions

Vlado
-- 
Vladimir Batagelj, University of Ljubljana, FMF, Department of Mathematics
  Jadranska 19, 1000 Ljubljana, Slovenia
http://vlado.fmf.uni-lj.si