{
  "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"
    }
  }
}