Computational Complexity of Solving Complex Problems

The notion of computational complexity is looked at as if it were a road along which we encounter several cognitive and operational obstacles. Some of these are difficult to anticipate, to prevent or solve. The study focuses on cases where the need to anticipate and solve is unavoidable. Three categories of such obstacles are discussed.

The first refers to the precise meaning of 'cognitive complexity' and what kind of problems does it rise. Here the discussion is centred on extending tractability of problems by means of identifying and solving circularities whenever they occur. The second enlarges on the accurate translation or transfer of the cognitive complexity into the computational one. The third obstacle is encountered when tractability, and circularity in particular, become so unavoidable that they need be anticipated which, in turn, is a prerequisite of designing the research programmes of particularly complex problems.

The problems considered to be extremely complex are those generated by 'scientifically-based human intervention'. Because of this, and the above technicalities, these problems are anything but disciplinary. A more precise idea of what means 'interdisciplinary' as a counterpart of 'undisciplinary' is given.

The study aims at correcting a status quo which complexity-related tractability and circularity are either neglected or mistakenly regarded as a technicality such as the quantitative limit of computation. The far-reaching aim is to reconsider the legitimacy and the terms in which we think of a 'science of complexity', and the extent to which cybernetics - third-order cybernetics, eventually - becomes the very core of this science.