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