Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
376882 | Artificial Intelligence | 2014 | 12 Pages |
Abstract
Unbiased black-box complexity was introduced as a refined complexity model for random-ized search heuristics (Lehre and Witt (2012) [24]). For several problems, this notion avoids the unrealistically low complexity results given by the classical model of Droste et al. (2006) [10].We show that for some problems the unbiased black-box complexity remains artificially small. More precisely, for two different formulations of an NPNP-hard subclass of the well-known Partition problem, we give mutation-only unbiased black-box algorithms having complexity O(nlogn)O(nlogn). This indicates that also the unary unbiased black-box complexity does not give a complete picture of the true difficulty of this problem for randomized search heuristics.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Benjamin Doerr, Carola Doerr, Timo Kötzing,