Existentially Restricted Quantified Constraint Satisfaction

Simple item page
dc.creatorChen, Hubie
dc.date2005-06-14
dc.date.accessioned2026-07-07T03:23:08Z
dc.date.available2026-07-07T03:23:08Z
dc.descriptionThe quantified constraint satisfaction problem (QCSP) is a powerful framework for modelling computational problems. The general intractability of the QCSP has motivated the pursuit of restricted cases that avoid its maximal complexity. In this paper, we introduce and study a new model for investigating QCSP complexity in which the types of constraints given by the existentially quantified variables, is restricted. Our primary technical contribution is the development and application of a general technology for proving positive results on parameterizations of the model, of inclusion in the complexity class coNP.
dc.identifierhttps://arxiv.org/abs/cs/0506059
dc.identifierhttp://arxiv.org/abs/cs/0506059
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32825
dc.subjectComputational Complexity
dc.subjectLogic in Computer Science
dc.titleExistentially Restricted Quantified Constraint Satisfaction
dc.typetext

Files

Collections

arXiv