A Complex-Networks View of Hard Combinatorial Search Spaces

摘要: According to worst-case complexity analysis, difficult combinatorial problems are those for which no polynomial-time algorithms known (see, instance, [15]). Thus, according this point of view, large enough instances these cannot be solved in reasonable time. The mathematical analysis is primarily based on decision problems, i.e. that require a yes/no answer [7, 15], but the theory can readily extended optimization [16], roughly speaking, we seek solution with an associated minimum or maximum cost, ones will dealt here.