Cognitive complexity is a psychological characteristic or psychological variable that indicates how complex or simple is the frame and perceptual skill of a person. A person who measures high on cognitive complexity tends to perceive nuances and subtle differences which a person with a lower measure, indicating a less complex cognitive structure for the task or activity, does not.
Used as part of one of the several variations of the viable non-empirical evaluation model GOMS (Goals, Operators, Methods, and Selection rules); in particular the GOMS/CCT methodology.
Cognitive complexity can have various meanings:
* the number of mental structures we use, how abstract they are, and how elaborately they interact to shape our perceptions.
* "an individual-difference variable associated with a broad range of communication skills and related abilities ... [which] indexes the degree of differentiation, articulation, and integration within a cognitive system". 
The concept was proposed by James Bieri in 1955.
For example, in his book Blink: The Power of Thinking without Thinking, Malcolm Gladwell discusses the differences between people with high cognitive complexity versus low cognitive complexity, though he does not use that term, with examples of the detection of art forgery as well as a discussion of taste tests and the differences between trained, experienced tasters versus untrained tasters. Art historians reviewing a sculpture felt a sense of wrongness about the sculpture, perceiving subtle differences between the actual sculpture and what the piece was represented to be, though they were unable to actually identify the root of their unease. Further investigation finally revealed that the piece was a well done forgery. A second example from the book involves a discussion of cola taste tests comparing how professional tasters do taste tests versus how untrained people taste.