The query complexity of a permutation-based variant of Mastermind - École polytechnique Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2019

The query complexity of a permutation-based variant of Mastermind

Résumé

We study the query complexity of a permutation-based variant of the guessing game Mastermind. In this variant, the secret is a pair (z, π) which consists of a binary string z ∈ {0, 1} n and a permutation π of [n]. The secret must be unveiled by asking queries of the form x ∈ {0, 1} n. For each such query, we are returned the score f z,π (x) := max{i ∈ [0..n] | ∀j ≤ i : z π(j) = x π(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 π. The goal is to minimize the number of queries needed to identify (z, π). This problem originates from the study of black-box optimization heuristics, where it is known as the LeadingOnes problem. In this work, we prove matching upper and lower bounds for the deterministic and ran-domized query complexity of this game, which are Θ(n log n) and Θ(n log log n), respectively.
Fichier principal
Vignette du fichier
2018_DAM_LeadingOnes_R1.pdf (462.74 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02077639 , version 1 (19-07-2019)

Identifiants

Citer

Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Doerr, Kasper Green Larsen, et al.. The query complexity of a permutation-based variant of Mastermind. Discrete Applied Mathematics, 2019, ⟨10.1016/j.dam.2019.01.007⟩. ⟨hal-02077639⟩
197 Consultations
113 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More