Artikel
The exact query complexity of yes-no permutation mastermind
Mastermind is famous two-player game. The first player (codemaker) chooses a secret code which the second player (codebreaker) is supposed to crack within a minimum number of code guesses (queries). Therefore, the codemaker's duty is to help the codebreaker by providing a well-defined 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 the codemaker only indicates if a query contains any correct position at all. For this Mastermind version with n positions and kÏn colors and ℓ:=k+1−n , we prove a lower bound of ∑kj=ℓlog2j and an upper bound of nlog2n+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 Θ(nlogn) queries.
- Language
-
Englisch
- Bibliographic citation
-
Journal: Games ; ISSN: 2073-4336 ; Volume: 11 ; Year: 2020 ; Issue: 2 ; Pages: 1-11 ; Basel: MDPI
- Classification
-
Wirtschaft
- Subject
-
Mastermind
permutation
query complexity
- Event
-
Geistige Schöpfung
- (who)
-
el Ouali, Mourad
Sauerland, Volkmar
- Event
-
Veröffentlichung
- (who)
-
MDPI
- (where)
-
Basel
- (when)
-
2020
- DOI
-
doi:10.3390/g11020019
- Handle
- Last update
-
10.03.2025, 11:42 AM CET
Data provider
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. If you have any questions about the object, please contact the data provider.
Object type
- Artikel
Associated
- el Ouali, Mourad
- Sauerland, Volkmar
- MDPI
Time of origin
- 2020
Other Objects (12)
The Exact Query Complexity of Yes-No Permutation Mastermind
Exact Cardinality Query Optimization with Bounded Execution Cost
Permutation complexity in dynamical systems : ordinal patterns, permutation entropy and all that
On the Complexity of Temporal Query Answering
On the relational complexity of a finite permutation group
On the Query Complexity of Black-Peg AB-Mastermind
On the query complexity of Black-Peg AB-mastermind
The communication complexity of the Exact-N Problem revisited
CROSSING Winter School 2016: Query Complexity and Lower Bounds (1)
CROSSING Winter School 2016: Query Complexity and Lower Bounds (2)
Counting Problems on Quantum Graphs : Parameterized and Exact Complexity Classifications
Exact algorithms based on specific complexity measures for hard problems
The Exact Query Complexity of Yes-No Permutation Mastermind
Exact Cardinality Query Optimization with Bounded Execution Cost
Permutation complexity in dynamical systems : ordinal patterns, permutation entropy and all that
On the Complexity of Temporal Query Answering
On the relational complexity of a finite permutation group
On the Query Complexity of Black-Peg AB-Mastermind
On the query complexity of Black-Peg AB-mastermind
The communication complexity of the Exact-N Problem revisited
CROSSING Winter School 2016: Query Complexity and Lower Bounds (1)
CROSSING Winter School 2016: Query Complexity and Lower Bounds (2)
Counting Problems on Quantum Graphs : Parameterized and Exact Complexity Classifications
Exact algorithms based on specific complexity measures for hard problems
The Exact Query Complexity of Yes-No Permutation Mastermind
Exact Cardinality Query Optimization with Bounded Execution Cost
Permutation complexity in dynamical systems : ordinal patterns, permutation entropy and all that
On the Complexity of Temporal Query Answering
On the relational complexity of a finite permutation group
On the Query Complexity of Black-Peg AB-Mastermind
On the query complexity of Black-Peg AB-mastermind
The communication complexity of the Exact-N Problem revisited
CROSSING Winter School 2016: Query Complexity and Lower Bounds (1)
CROSSING Winter School 2016: Query Complexity and Lower Bounds (2)
Counting Problems on Quantum Graphs : Parameterized and Exact Complexity Classifications