Conundrum of combinatorial complexity

Abstract—This paper examines fundamental problems underlying difficulties encountered by pattern recognition algorithms, neural networks, and rule systems. These problems are manifested as combinatorial complexity of algorithms, of their computational or training requirements. The paper relates particular types of complexity problems to the roles of a priori knowledge and adaptive learning. Paradigms based on adaptive learning lead to the complexity of training procedures, while nonadaptive rule-based paradigms lead to complexity of rule systems. Model-based approaches to combining adaptivity with a priori knowledge lead to computational complexity. Arguments are presented for the Aristotelian logic being culpable for the difficulty of combining adaptivity and a priority. The potential role of the fuzzy logic in overcoming current difficulties is discussed. Current mathematical difficulties are related to philosophical debates of the past. Index Terms—Pattern recognition, neural networks, rule systems, complexity, training, learning, a priori knowledge, fuzzy logic, Aristotelian logic ——————— — F ———————