The query complexity of a permutation-based variant of mastermind

DOI10.1016/J.DAM.2019.01.007MaRDI QIDQ1741495zbMATH OpenOpenAlexWikidataFDO

Authors Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Doerr, Kasper Green Larsen, K. Mehlhorn

Publication date 3 May 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.08480

zbMATH Keywords

query complexityblack-box complexity\textsc{LeadingOnes}hidden permutation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04) Combinatorial games (91A46)

Abstract: We study the query complexity of a permutation-based variant of the guessing game Mastermind. In this variant, the secret is a pair $(z,pi)$ which consists of a binary string $zin{0,1}^n$ and a permutation $pi$ of $[n]$. The secret must be unveiled by asking queries of the form $xin{0,1}^n$. For each such query, we are returned the score [ f_{z,pi}(x):= max { i in [0..n]mid forall j leq i: z_{pi(j)} = x_{pi(j)}},;] i.e., the score of $x$ is the length of the longest common prefix of $x$ and $z$ with respect to the order imposed by $pi$. The goal is to minimize the number of queries needed to identify $(z,pi)$. This problem originates from the study of black-box optimization heuristics, where it is known as the extsc{LeadingOnes} problem. In this work, we prove matching upper and lower bounds for the deterministic and randomized query complexity of this game, which are $Theta(nlogn)$ and $Theta(nloglogn)$, respectively.

Recommendations

• Query complexity of mastermind variants
• The exact query complexity of yes-no permutation mastermind
• Bounds for the static permutation mastermind game
• The query complexity of finding a hidden permutation
• scientific article; zbMATH DE number 7650068
• Solving static permutation mastermind using \(O(n \log n)\) queries
• On the algorithmic complexity of the Mastermind game with black-peg results
• On the query complexity of black-peg AB-mastermind
• On the number of queries necessary to identify a permutation
• scientific article; zbMATH DE number 4053621

Cites work

• scientific article; zbMATH DE number 3194843 (Why is no real title available?)
• Black-box search by unbiased variation
• Faster black-box algorithms through higher arity operators
• Mastermind
• On the analysis of the \((1+1)\) evolutionary algorithm
• The Complexity of Enumeration and Reliability Problems
• The \((1+1)\) elitist black-box complexity of LeadingOnes
• The query complexity of finding a hidden permutation
• Upper and lower bounds for randomized search heuristics in black-box optimization

Cited in

(12)

• On the algorithmic complexity of the Mastermind game with black-peg results
• Mutation rate control in the \((1+\lambda)\) evolutionary algorithm with a self-adjusting lower bound
• Solving static permutation mastermind using \(O(n \log n)\) queries
• Choosing the right algorithm with hints from complexity theory
• Quantum algorithm for learning secret strings and its experimental demonstration
• scientific article; zbMATH DE number 7650068 (Why is no real title available?)
• The query complexity of finding a hidden permutation
• Working principles of binary differential evolution
• The exact query complexity of yes-no permutation mastermind
• The runtime of the compact genetic algorithm on jump functions
• On the query complexity of black-peg AB-mastermind
• Fourier analysis meets runtime analysis: precise runtimes on plateaus

This page was built for publication: The query complexity of a permutation-based variant of mastermind

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1741495)