{
"id": "2003.11538",
"version": "v1",
"published": "2020-03-25T17:57:46.000Z",
"updated": "2020-03-25T17:57:46.000Z",
"title": "The Exact Query Complexity of Yes-No Permutation Mastermind",
"authors": [
"Moura El Ouali",
"Volkmar Sauerland"
],
"comment": "12 pages, 2 figures, submitted to GAMES",
"categories": [
"cs.DS",
"math.CO"
],
"abstract": "Mastermind is famous two-players game. The ?rst player (codemaker) chooses a secret code which the second player (codebreaker) is supposed to crack within a minimum number of code guesses (queries). Therefore, codemaker's duty is to help codebreaker by providing a well-de?ned error measure between the secret code and the guessed code after each query. We consider a variant, called Yes-No AB-Mastermind, where both secret code and queries must be repetition-free and the provided information by codemaker only indicates if a query contains any correct position at all. For this Mastermind version with n positions and $k\\le n$ colors we prove a lower bound of $\\log_2(k+1-n)+\\log_2(k+2-n)+\\dots+\\log_2(k)$ and an upper bound of $n\\log_2(n)+k$ on the number of queries necessary to break the secret code. For the important case $k=n$, where both secret code and queries represent permutations, our results imply an exact asymptotic complexity of $\\Theta(n\\log_2(n))$ queries.",
"revisions": [
{
"version": "v1",
"updated": "2020-03-25T17:57:46.000Z"
}
],
"analyses": {
"subjects": [
"91A46"
],
"keywords": [
"yes-no permutation mastermind",
"exact query complexity",
"secret code",
"exact asymptotic complexity",
"queries represent permutations"
],
"note": {
"typesetting": "TeX",
"pages": 12,
"language": "en",
"license": "arXiv",
"status": "editable"
}
}
}