Finite domain constraint satisfaction using quantum computation

被引：0
|
作者：
Angelsmark, O [1 ]
Dahllöf, V [1 ]
Jonsson, P [1 ]
机构：
[1] Linkoping Univ, Dept Comp & Informat Sci, SE-58183 Linkoping, Sweden
来源：
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2002 | 2002年 / 2420卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We present a quantum algorithm for finite domain constraint solving, where the constraints have arity 2. It is complete and runs in O(([d/2])(n/2)) time, where d is size of the domain of the variables and n the number of variables. For the case of d = 3 we provide a method to obtain an upper time bound of O(8(n/8)) approximate to O(1.2968(n)). Also for d = 5 the upper bound has been improved. Using this method in a slightly different way we can decide 3-colourability in O(1.2185(n)) time.
引用
收藏
页码：93 / 103
页数：11
相关论文
共 50 条
  • [1] Using finite domains in constraint satisfaction problem
    Popescu, I
    INTELLIGENT INFORMATION PROCESSING II, 2005, 163 : 351 - 354
  • [2] Domain dependence in parallel constraint satisfaction
    1600, Morgan Kaufmann Publ Inc, San Mateo, CA, USA (01):
  • [3] Domain transmutation in constraint satisfaction problems
    Bowen, J
    Likitvivatanavong, C
    PROCEEDING OF THE NINETEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND THE SIXTEENTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE, 2004, : 149 - 154
  • [4] Constraint satisfaction problems and finite algebras
    Bulatov, AA
    Krokhin, AA
    Jeavons, P
    AUTOMATA LANGUAGES AND PROGRAMMING, 2000, 1853 : 272 - 282
  • [5] NEURAL NETWORKS FOR FINITE CONSTRAINT SATISFACTION
    MONFROGLIO, A
    NEURAL COMPUTING & APPLICATIONS, 1995, 3 (02): : 78 - 100
  • [6] Locally Finite Constraint Satisfaction Problems
    Klin, Bartek
    Kopczynski, Eryk
    Ochremiak, Joanna
    Torunczyk, Szymon
    2015 30TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2015, : 475 - 486
  • [7] On the computation of local interchangeability in discrete constraint satisfaction problems
    Choueiry, BY
    Noubir, G
    FIFTEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE (AAAI-98) AND TENTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICAL INTELLIGENCE (IAAI-98) - PROCEEDINGS, 1998, : 326 - 333
  • [8] Synergetic computation for constraint satisfaction problems involving continuous and fuzzy variables by using occam
    Katai, Osamu
    Shigeo, Matsubara
    Hiroshi, Masuichi
    Masaaki, Ida
    Tetsuo, Sawaragi
    Sosuke, Iwai
    International Conference on Applications of Transputers, 1992, 27
  • [9] Complexity of Infinite-Domain Constraint Satisfaction
    Krokhin, Andrei
    Bodirsky, Manuel
    BULLETIN OF SYMBOLIC LOGIC, 2024, 30 (03) : 431 - 432
  • [10] Promise and Infinite-Domain Constraint Satisfaction
    Mottet, Antoine
    32ND EACSL ANNUAL CONFERENCE ON COMPUTER SCIENCE LOGIC, CSL 2024, 2024, 288
12345