Thumbnail
Access Restriction
Subscribed

Author Chen, Hubie
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2009
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Constraint satisfaction ♦ Schaefer's theorem ♦ Polymorphisms ♦ Propositional logic ♦ Quantified formulas
Abstract An emerging area of research studies the complexity of constraint satisfaction problems under restricted constraint languages. This article gives a self-contained, contemporary presentation of Schaefer's theorem on Boolean constraint satisfaction, the inaugural result of this area, as well as analogs of this theorem for quantified formulas. Our exposition makes use of and may serve as an introduction to logical and algebraic tools that have recently come into focus.
ISSN 03600300
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2009-12-01
Publisher Place New York
e-ISSN 15577341
Journal ACM Computing Surveys (CSUR)
Volume Number 42
Issue Number 1
Page Count 32
Starting Page 1
Ending Page 32


Open content in new tab

   Open content in new tab
Source: ACM Digital Library