Abstract: Complex problem-solving (CPS) is as an area of cognitive science that has received a good amount of attention, but theories in the field have not progressed accordingly. The reasons could be the lack of good definitions and classifications of the tasks (taxonomies). Although complexity is a term used pervasively in psychology and is operationalized in different ways, there are no psychological theories of complexity. The definition of problem-solving has been changed in the past to reflect the varied interests of the researchers and has lost its initial concreteness. These two facts together make it difficult to define CPS or make clear if CPS should reuse the theory and methods of classical problem-solving or on the contrary should build a theoretical structure starting from scratch. A taxonomy is offered of tasks using both formal features and psychological features that are theory-independent that could help compare the CPS tasks used in the literature. The adequateness is also reviewed of the most extended definitions of CPS and conclude that they are in serious need of review, since they cover tasks that are not considered problem-solving by their own authors or are not complex, but ignore others that should clearly be included.