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 条
  • [31] Lightning electromagnetic fields computation using time domain finite element method
    de Miranda, GC
    Ribeiro, EJ
    2005 IEEE/ACES International Conference on Wireless Communications and Applied Computational Electromagnetics, 2005, : 301 - 304
  • [32] Driver Assistance Control based on Model Predictive Computation of Constraint Satisfaction
    Yamaguchi, Takuma
    Tatebe, Jumpei
    Okuda, Hiroyuki
    Tazaki, Yuichi
    Suzuki, Tatsuya
    Ito, Takafumi
    Muto, Kenji
    2015 IEEE 18TH INTERNATIONAL CONFERENCE ON INTELLIGENT TRANSPORTATION SYSTEMS, 2015, : 1304 - 1310
  • [33] CP(graph): Introducing a graph computation domain in constraint programming
    Dooms, G
    Deville, Y
    Dupont, P
    PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2005, PROCEEDINGS, 2005, 3709 : 211 - 225
  • [34] Rigorous domain triangulation for the finite element computation
    Ozaki, Katsuhisa
    Liu, Xuefeng
    JSIAM LETTERS, 2024, 16 : 69 - 72
  • [35] Using constraint satisfaction for view update
    Shu, H
    JOURNAL OF INTELLIGENT INFORMATION SYSTEMS, 2000, 15 (02) : 147 - 173
  • [36] Geometric constraint satisfaction using GAAA
    Cao, C. H.
    Li, W. H.
    Yi, R. Q.
    COMPUTATIONAL METHODS, PTS 1 AND 2, 2006, : 977 - 981
  • [37] Using constraint satisfaction in genetic algorithms
    Kowalczyk, R
    ANZIIS 96 - 1996 AUSTRALIAN NEW ZEALAND CONFERENCE ON INTELLIGENT INFORMATION SYSTEMS, PROCEEDINGS, 1996, : 272 - 275
  • [38] Using Constraint Satisfaction for View Update
    Hua Shu
    Journal of Intelligent Information Systems, 2000, 15 : 147 - 173
  • [39] DeepSaDe: Learning Neural Networks That Guarantee Domain Constraint Satisfaction
    Goyal, Kshitij
    Dumancic, Sebastijan
    Blockeel, Hendrik
    THIRTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 38 NO 11, 2024, : 12199 - 12207
  • [40] The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
    Barto, Libor
    Pinsker, Michael
    PROCEEDINGS OF THE 31ST ANNUAL ACM-IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2016), 2016, : 615 - 622
12345