# Combinatorial Complexity

Combinatorial complexity is a quantitative assessment of how hard a problem is to solve. Typical combinatorial problems are exponential in the size of their input, meaning that it would take an exponential amount of time to solve the problem, hence only very small instances of the problem are computable within a reasonable amount of time.

Biochemical networks that are useful in modeling complex adaptive systems such as interacting proteins involved in cellular signaling, have routinely proved to be difficult to model due to their combinatorial complexity. Interactions among proteins for example depend on both the molecular content and context. Each of these may influence rates of attendant effects, for example enzymatic actions or binding between different domains. A purely physics based approach requires accounting for all possible states for each molecular actor and all possible multicomponent complexes of molecules. This approach yields an accurate but computationally infeasible model that is hampered by the combinatorics of examining all possible combinations of actors, their states, the energy or rate of each possible reaction and all the possible resultant biochemical species. At each time step the growth of participating entities is at a minimum polynomial and in most cases exponential.