Hybrid Tractable Classes of Binary Quantified Constraint Satisfaction Problems

Details Hybrid Tractable Classes of Binary Quantified Constraint Satisfaction Problems Hybrid Tractable Classes of Binary Quantified Constraint Satisfaction Problems

2011-04-26

arxiv.org/abs/1104.4910v1

Computer Science

Artificial Intelligence

Scientific paper

In this paper, we investigate the hybrid tractability of binary Quantified Constraint Satisfaction Problems (QCSPs). First, a basic tractable class of binary QCSPs is identified by using the broken-triangle property. In this class, the variable ordering for the broken-triangle property must be same as that in the prefix of the QCSP. Second, we break this restriction to allow that existentially quantified variables can be shifted within or out of their blocks, and thus identify some novel tractable classes by introducing the broken-angle property. Finally, we identify a more generalized tractable class, i.e., the min-of-max extendable class for QCSPs.

Affiliated with

Also associated with

No associations

Rating

Hybrid Tractable Classes of Binary Quantified Constraint Satisfaction Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hybrid Tractable Classes of Binary Quantified Constraint Satisfaction Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hybrid Tractable Classes of Binary Quantified Constraint Satisfaction Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-296138