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)
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