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
Permutation complexity in dynamical systems : ordinal patterns, permutation entropy and all that
Exact Cardinality Query Optimization with Bounded Execution Cost
On the Complexity of Temporal Query Answering
Exploring the Complexity of Event Query Discovery
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 complexity of gene expression dynamics revealed by permutation entropy
CROSSING Winter School 2016: Query Complexity and Lower Bounds (1)
CROSSING Winter School 2016: Query Complexity and Lower Bounds (2)
Logarithmic Query Complexity for Approximate Nash Computation in Large Games
The Exact Query Complexity of Yes-No Permutation Mastermind
Permutation complexity in dynamical systems : ordinal patterns, permutation entropy and all that
Exact Cardinality Query Optimization with Bounded Execution Cost
On the Complexity of Temporal Query Answering
Exploring the Complexity of Event Query Discovery
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 complexity of gene expression dynamics revealed by permutation entropy
CROSSING Winter School 2016: Query Complexity and Lower Bounds (1)
CROSSING Winter School 2016: Query Complexity and Lower Bounds (2)
Logarithmic Query Complexity for Approximate Nash Computation in Large Games
The Exact Query Complexity of Yes-No Permutation Mastermind
Permutation complexity in dynamical systems : ordinal patterns, permutation entropy and all that
Exact Cardinality Query Optimization with Bounded Execution Cost
On the Complexity of Temporal Query Answering
Exploring the Complexity of Event Query Discovery
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 complexity of gene expression dynamics revealed by permutation entropy
CROSSING Winter School 2016: Query Complexity and Lower Bounds (1)
CROSSING Winter School 2016: Query Complexity and Lower Bounds (2)