The query complexity of a permutation-based variant of Mastermind

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, π) 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.