What are the characteristics that make complex problem solving complex? In real-world problem-solving tasks that many people call "complex" (like flying a jet, programming, fixing a car, fighting a fire - the type investigated by the naturalistic decision making community) what are the key characteristics that separate problem solving in these types of tasks and problem solving in "toy" or "experiment" tasks where one or two stimuli are presented to participants? 

What are the characteristics that make complex problem solving complex?

Are there levels of complexity that can capture the differences?
The complexity of the environment certainly is an issue. According to AI - A modern approach, the environment may be


observable / partly observable
deterministic / stochastic / strategic
episodic / sequential
static / dynamic
discrete / continuous
single agent / multiple agent


See also WikiDoc for a short overview.
In my oppinion, these criteria apply also to human problem
solving.

Another issue is the type of problem to be solved.
A measure for complexity may be the number of steps
that must be anticipated to solve the problem, e.g.
solving a chess endgame is more complex than solving
tic tac toe.