Hybrid Tractable Class for Quantified Constraint Satisfaction Problems
Author:
Affiliation:

Clc Number:

TP181

Fund Project:

National Natural Science Foundation of China (61402070, 61672122, 61602077)

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    Quantified constraint satisfaction problem (QCSP) is a central problem in artificial intelligence and automated reasoning. The tractable class is an important method to analyze its computation complexity. This study proposed a new method to determine tractability of quantified variables by analyzing constraint structures and the ordering of universally quantified variables in the prefix on a binary QCSP. Based on this method, the existing tractable class was extended with the broken-triangle property, and then a more generalized hybrid tractable class was proposed. Furthermore, an application was presented that was identifying backdoor sets through the new tractable class, and the experimental results were analyzed to show the size of backdoor sets identified by those hybrid tractable classes. To perform the experiment, a state-of-the-art QCSP solver was modified based on a backtracking algorithm by integrating a backdoor set detection module, and the advantage of the new generalized tractable class is shown where the size of backdoor set identified by it is smaller than the existing one on randomly generated instances. Finally, it is indicated that the method proposed in this study can be employed to extend other hybrid tractable classes.

    Reference
    Related
    Cited by
Get Citation

高健,陈荣,李辉.一种量词约束满足问题的混合易解子类.软件学报,2019,30(12):3590-3604

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:December 28,2017
  • Revised:March 17,2018
  • Adopted:
  • Online: December 05,2019
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063