Computational complexity of combinatorial and graph theoretic problems

点击翻译按钮获取中文摘要

The speed and power of modern computers is truly impressive. So much so, that one might believe any reasonable problem can be solved, even by brute force, in reasonable time. Surprisingly this is not the case. Consider the problem of assigning resources to a collection of users, for example scheduling teams in a round robin tournament. The goal is to assign the resources in the most efficient way possible, subject to constraints restricting the assignments. This a Constraint Satisfaction Problem or CSP. For a fast computer to exhaustively search through all the possible combinations looking for the optimum assignment could take thousands of years. This is an example of "combinatorial explosion"; the sheer number of combinations defeats brute force solutions. More efficient algorithms, if they exist, must be employed.