y0 icon indicating copy to clipboard operation
y0 copied to clipboard

Implement metric for expression complexity

Open cthoyt opened this issue 4 years ago • 0 comments

Carette (2004) provides a formal definition for simplification in the context of Computer Algebra Systems (CAS) that operate on algebraic expressions. Modern CAS systems such as Mathematica (Wolfram Research Inc., 2015) and Maxima (Maxima, 2014) implement techniques for symbolic simplification. Bailey et al. (2014) and references therein discuss simplification techniques in CAS systems further.

The algorithm should take the following form:

from y0.dsl import Expression

def complexity(expression: Expression) -> int:
    """Measure the complexity of the expression."""
    raise NotImplementedError

Alternatively, the complexity could return a float.

cthoyt avatar Jan 20 '21 13:01 cthoyt