Categories and Subject Descriptors: F.1.3 [Computation by Abstract Devices]: Complexity Classes -- reducibility and completeness; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- complexity of proof procedures; F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic; G.2.1 [Discrete Mathematics]: Combinatorics
General Terms: Algorithms, Languages, Theory, Verification
Additional Key Words and Phrases: Complexity, constraint satisfaction problem, indicator problem, NP-completeness
Selected references
- E. F. Codd. A relational model of data for large shared data banks. Communications of the ACM, 13(6):377-387, June 1970. Also published in/as: `Readings in Database Systems', M. Stonebraker, Morgan-Kaufmann, 1988, pp. 5-15.
- Tomás Feder and Moshe Y. Vardi. Monotone monadic SNP and constraint satisfaction. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 612-622, San Diego, California, 16-18 May 1993.
- Eugene C. Freuder. A sufficient condition for backtrack-bounded search. Journal of the ACM, 32(4):755-761, October 1985.
- Peter B. Ladkin and Roger D. Maddux. On binary constraint problems. Journal of the ACM, 41(3):435-469, May 1994.
- Thomas J. Schaefer. The complexity of satisfiability problems. In Conference Record of the Tenth Annual ACM Symposium on Theory of Computing, pages 216-226, San Diego, California, 1-3 May 1978.