Fixed complexity problems

Fixed complexity problems are problems in which the only requirement is to find a suitable set of values for a fixed set of parameters. Problems falling into this class include

• Many continuous optimisation problems, where the aim is simply to find real-number values for a set of parameters x1,…,xn that optimise the value of some function f(x1,…,xn)
• Some discrete optimisation problems, where the aim is again to find integer values for a set of parameters x1,…,xn that optimise the value of some function f(x1,…,xn)
  • Even many combinatorial problems can be cast in this light
• Linear regression, where the aim is to find a fixed set of linear coefficients relating the variables under consideration
• Simple propositional learning problems generally fall into this class

Methods for solving such problems include

• Complete search (depth, breadth first,….)
• Heuristic search (A*, branch and bound,….)
• 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 (so we have done some work on dynamic travelling salesman problems, dynamic ant clustering,…)
• Problems belonging to a family of problems, so tough versions can be solved incrementally from first solving simpler ones