Variable complexity problems are problems in which the main problem is to find a suitable set of values for a set of parameters, but we don't know how many. However we already know the relationships between the parameters. Problems falling into this class include
A few optimisation problems, where the aim is to find real-number coefficients x1,…,xn where we don't know how large n needs to be beforehand - this includes cases such as power or fourier series approximations
Some discrete optimisation problems, we may not know ahead of time how many parameters x1,…, are required
Polynomial regression, where we don't know ahead of time how high degree polynomial is required to get an acceptable fit
Most interesting attribute learning problems fall into this class - decision trees, decision rules etc
While solutions aren't completely unstructured, there are many transformation symmetries (transitivity, commutativity,…) so discovering the structure is generally not the hard part of the problem
Methods for solving such problems include
Gradient descent and similar deterministic eager search methods
Stochastic search (simulated annealing, tabu search, genetic algorithms)
While this isn't the primary focus of research in the structural complexity lab, we do some research in these areas from time to time; we tend to be more interested in
Dynamic problems, where the optimal solution changes with time
Problems belonging to a family of problems, so tough versions can be solved incrementally from first solving simpler ones