Vi visar att den obegränsade svarta lådan komplexiteten hos den n-dimensionella XOR- och permutation-invarianta LeadingOnes funktionsklass är O(n log(n)/ log log n). Detta visar att den senaste naturliga utseende O (n log n) bundna är inte tight. Den Black-box optimeringsalgoritm som leder till denna gräns kan implementeras på ett sätt som endast 3-är opartiska variationsoperatörer används. Därför är vår gräns också giltig för den opartiska Black-box komplexitet som nyligen infördes av Lehre och Witt. Gränsen förblir också giltig om vi inför den ytterligare begränsningen att Black-box algoritmen inte har tillgång till de objektiva värdena utan endast till deras relativa ordning (rankning-baserad svart-box komplexitet).
Den algoritm som uppnår den O(n log n/ log log n) som anges i avsnitt 1.1 kan implementeras som en ternära objektiv en REF.
Black-Box Complexity: Breaking the $O(n \log n)$ Barrier of LeadingOnes
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}