Towards Fixed-Target Black-Box Complexity Analysis

Dmitry Vinokurov, Maxim Buzdalov*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)


Recently, fine-grained measures of performance of randomized search heuristics received attention in the theoretical community. In particular, some results were proven specifically for fixed-target runtime analysis. However, this research domain still lacks an important counterpart, namely, the (black-box) complexity analysis, which shall augment runtime analyses of particular algorithms with the bounds on what can be achieved with the best possible algorithms. This paper makes few first steps in this direction. We prove upper and lower bounds on the fixed-target black-box complexity of the standard benchmark function OneMax given the problem size n and the target fitness k that we want to achieve. On the way to these bounds, we prove a general lower bound theorem suitable to derive bounds not only in fixed-target settings, but also in settings where a problem instance may have multiple optima.

Original languageEnglish
Title of host publicationParallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings
EditorsGünter Rudolph, Anna V. Kononova, Hernán Aguirre, Pascal Kerschke, Gabriela Ochoa, Tea Tušar
PublisherSpringer Nature
Number of pages12
ISBN (Print)9783031147203
Publication statusPublished - 10 Sept 2022
Event17th International Conference on Parallel Problem Solving from Nature, PPSN 2022 - Dortmund, Germany
Duration: 10 Sept 202214 Sept 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13399 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference17th International Conference on Parallel Problem Solving from Nature, PPSN 2022
Period10 Sept 202214 Sept 2022


  • Black-box complexity
  • Fixed-target analysis
  • OneMax


Dive into the research topics of 'Towards Fixed-Target Black-Box Complexity Analysis'. Together they form a unique fingerprint.

Cite this