MariaAnt provided a relevant definition of complex problem solving in the answer to the question, "Research operationalizing so-called strategic thinking?" based on Frensch and Funke (1995).
[Complex problem solving] occurs to overcome barriers between a given state and a desired goal state by means of behavioral and/or cognitive, multistep activities. The given state, goal state, and barriers between given state and goal state are complex, change dynamically during problem solving, and are intransparent. The exact properties of the given state, goal state, and barriers are unknown to the solver at the outset. CPS implies the efficient interaction between a solver and the situational requirements of the task, and involves a solver’s cognitive, emotional, personal, and social abilities and knowledge.
Background
Complexity in science
In modern scientific jargon, complexity and the quality of being complex can have a number of different meanings, depending on the field and subject of interest. These can be traced back to a historical distinction between organized and disorganized complexity (Weaver, 1948). In the cognitive sciences, a problem is complex (sometimes called ill-defined) if the relations between initial state, goal state and space of intermediate states are interdependent, nonlinear and/or the state properties are unknown for the solver. Generally, something (such as a problem) is "complex" when it has a moderate number of time- and inter-dependent variables.
Organized or disorganized?
Problems of disorganized complexity, Weaver argued, were characterized by large numbers of variables and erratic behavior, with the analysis of telephone exchanges being a prototypical example of such problems. Meanwhile, problems of organized complexity were argued to be characterized by “dealing simultaneously with a sizable number of factors which are interrelated into an organic whole” and were exemplified by biological and social systems. Modern use of "complex" refers to (problems of) organized complexity, and this is also true in the cognitive sciences.
Levels of complexity
Complexity types and classes are studied within the context of many fields, but there is not much agreement on a universal framework we can use to objectively define levels of complexity. Neither is there agreement on how to measure complexity, though many measures have been proposed and used (Lloyd, 2001).
The closest thing to a universal framework is the mathematical study of complexity classes, which defines a large set of possible complexity classes in terms of how long time it would take a particular computational solver to solve the problem for a given input. The most famous of these classes are probably Polynomial-Time (P) and Nondeterministic Polynomial-Time (NP), as in "Does P = NP?" This is probably better covered by CSTheory than CogSci, but hopefully provides a place to start looking.
It may also be helpful to study the work of Herbert Simon, though covering his extensive contributions to complexity and problem solving are beyond the scope of this answer.
References
- Frensch, P. and Funke, J. (1995) Definitions, Traditions and a General Framework for Understanding Complex Problem Solving. In P. A. Frensch and
J. Funke (Eds.), Complex Problem Solving: The European Perspective.(Hillsdale, NJ, Lawrence Erlbaum). 3-25.
- Lloyd, S. (2001). Measures of complexity: a nonexhaustive list. IEEE Control Systems Magazine, 21(4), 7-8.
- Weaver, W. (1948). Science and complexity. American Scientist, 36(4), 536-544.