Memory-restricted black-box complexity of One Max

被引：6
|
作者：
Doerr, Benjamin [1 ]
Winzen, Carola [1 ]
机构：
[1] Max Planck Inst Informat, D-66123 Saarbrucken, Germany
来源：
INFORMATION PROCESSING LETTERS | 2012年 / 112卷 / 1-2期
关键词：
Algorithms; Black-box complexity; Query complexity; Bounded memory;
D O I：
10.1016/j.ipl.2011.10.004
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We show that the black-box complexity with memory restriction one of the n-dimensional ONEMAX function class is at most 2n. This disproves the Theta(n logn) conjecture of Droste, Jansen, and Wegener (Theory Computing Systems 39 (2006) 525-544). (C) 2011 Elsevier B.V. All rights reserved.
引用
收藏
页码：32 / 34
页数：3
相关论文
共 50 条
  • [1] One Max in Black-Box Models with Several Restrictions
    Doerr, Carola
    Lengler, Johannes
    GECCO'15: PROCEEDINGS OF THE 2015 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2015, : 1431 - 1438
  • [2] Ranking-Based Black-Box Complexity
    Doerr, Benjamin
    Winzen, Carola
    ALGORITHMICA, 2014, 68 (03) : 571 - 609
  • [3] The Unrestricted Black-Box Complexity of Jump Functions
    Buzdalov, Maxim
    Doerr, Benjamin
    Kever, Mikhail
    EVOLUTIONARY COMPUTATION, 2016, 24 (04) : 719 - 744
  • [4] Ranking-Based Black-Box Complexity
    Benjamin Doerr
    Carola Winzen
    Algorithmica, 2014, 68 : 571 - 609
  • [5] On the Black-Box Complexity of Correlation Intractability
    Doettling, Nico
    Mour, Tamer
    15TH INNOVATIONS IN THEORETICAL COMPUTER SCIENCE CONFERENCE, ITCS 2024, 2024,
  • [6] The quantum black-box complexity of majority
    Hayes, TP
    Kutin, S
    van Melkebeek, D
    ALGORITHMICA, 2002, 34 (04) : 480 - 501
  • [7] Reducing the arity in unbiased black-box complexity
    Doerr, Benjamin
    Winzen, Carola
    THEORETICAL COMPUTER SCIENCE, 2014, 545 : 108 - 121
  • [8] On the Black-Box Complexity of Sperner's Lemma
    Friedl, Katalin
    Ivanyos, Gabor
    Santha, Miklos
    Verhoeven, Yves F.
    THEORY OF COMPUTING SYSTEMS, 2009, 45 (03) : 629 - 646
  • [9] Parallel Black-Box Complexity With Tail Bounds
    Lehre, Per Kristian
    Sudholt, Dirk
    IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2020, 24 (06) : 1010 - 1024
  • [10] The (1+1) Elitist Black-Box Complexity of LeadingOnes
    Doerr, Carola
    Lengler, Johannes
    ALGORITHMICA, 2018, 80 (05) : 1579 - 1603
12345