Skip to main content


eCommons@Cornell

eCommons@Cornell >
Faculty of Computing and Information Science >
Computing and Information Science >
Computing and Information Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/5611
Title: Quantified Constraint Satisfaction Problems: Closure Properties, Complexity, and Proof Systems
Authors: Chen, Hubie
Keywords: computer science
technical report
Issue Date: 18-Apr-2003
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2003-1895
Abstract: There has been much prior work on understanding the complexity of the constraint satisfaction problem (CSP), a broad framework capturing many combinatorial problems. This paper studies a natural and strict generalization of the CSP, the quantified constraint satisfaction problem (QCSP). In the CSP, all variables are existentially quantified; in the QCSP, some variables may be universally quantified. Our contributions include proof systems for the QCSP and the identification of three broad tractable subclasses of the QCSP. Central to our study is the algebraic notion of closure properties of constraints, which has been previously used to study the CSP.
URI: http://hdl.handle.net/1813/5611
Appears in Collections:Computing and Information Science Technical Reports

Files in This Item:

File SizeFormat
TR2003-1895.ps255.16 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us