A proper complexity function is a function f mapping a natural number to a natural number such that:
If f and g are two proper complexity functions, then f + g, fg, and 2f are also proper complexity functions.
Similar notions include honest functions, space-constructible functions, and time-constructible functions.
Myashnikov, Alexei; Shpilrain, Vladimir; Ushakov, Vladimir (2008). Group-based Cryptography. Birkhauser. p. 28. ISBN 978-3-7643-8826-3.