Variable complexity problems

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
  • For example knapsack problems, stock cutting problems
• 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