Complexity of partition problems

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

Constraint satisfaction problems model many problems in scheduling, logistics, databases, and artificial intelligence. It has been observed that when the constraint language (or the constraint 'template') is fixed, the problems seem to fall into only two categories - polynomial time solvable or NP-complete. On the other hand, it is known that (unless P=NP) there must exist problems which are not solvable in polynomial time, but which are not quite NP-complete. Whether or not there are such 'intermediate' constraint satisfaction problems (with a fixed template) has become a very important open problem in theoretical computer science, driving much research effort based on algebra, analysis, logic, and combinatorics. Graphs seem to have an important role to play. Our results in graph theory have motivated the original problem, as well as several subsequent developments. It now appears that they will continue to motivate the research efforts. In this proposal, we propose research in the complexity of certain variants of graph homomorphism problems which would have implications for (variants of) general constraint satisfaction problems. These include list homomorphism, minimum cost homomorphism, and matrix partition problems.