Reasoning about knowledge and time in asynchronous systems
Joseph Y. Halpern, Moshe Y. Vardi
STOC 1988
A constraint-satisfaction problem is given by a pair I (the instance) and T (the template) of finite relational structures over the same vocabulary. The problem is satisfied if there is a homomorphism from 1 to T. It is well-known that the constraint-satisfaction problem is NP-complete. In practice, however, one often encounters the situation where the template T is fixed and it is only the instance I that varies. We define CSP to be the class of constraint-satisfaction problems with respect to fixed templates. It is easy to see that CSP is contained in NP and that CSP contains both problems in P and NP-complete problems. We pose the question whether every problem in CSP is either in P or is NP-complete, and attempt to classify which problems in CSP are in P and which are NP-complete.
Joseph Y. Halpern, Moshe Y. Vardi
STOC 1988
Moshe Y. Vardi
Information Processing Letters
Joseph Y. Halpern, Moshe Y. Vardi
Journal of Computer and System Sciences
Moni Naor, Larry Stockmeyer
STOC 1993