The complexity of recursive constraint satisfaction problems |
| |
Authors: | Victor W Marek Jeffrey B Remmel |
| |
Institution: | aDepartment of Computer Science, University of Kentucky, Lexington, KY 40506, USA;bDepartment of Mathematics, University of California, La Jolla, CA 92093, USA |
| |
Abstract: | We investigate the complexity of finding solutions to infinite recursive constraint satisfaction problems. We show that, in general, the problem of finding a solution to an infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through a recursive tree. We also identify natural classes of infinite recursive constraint satisfaction problems where the problem of finding a solution to the infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through finitely branching recursive trees or recursive binary trees. There are a large number of results in the literature on the complexity of the problem of finding an infinite path through a recursive tree. Our main result allows us to automatically transfer such results to give equivalent results about the complexity of the problem of finding a solution to a recursive constraint satisfaction problem. |
| |
Keywords: | Recursive constraint satisfaction problems Recursive trees Degrees of solutions |
本文献已被 ScienceDirect 等数据库收录! |
|