The Query Complexity of Finding a Hidden Permutation

DOI10.1007/978-3-642-40273-9_1zbMath1391.68044OpenAlexW1526420097MaRDI QIDQ2848962

Carola Doerr, Kurt Mehlhorn, Kasper Green Larsen, Benjamin Doerr, Peyman Afshani, Manindra Agrawal

Publication date: 13 September 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/11858/00-001M-0000-0025-0634-2

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Permutations, words, matrices (05A05)

Related Items

Exact learning of multitrees and almost-trees using path queries ⋮ Unnamed Item ⋮ The unbiased black-box complexity of partition is polynomial ⋮ From black-box complexity to designing new genetic algorithms ⋮ The query complexity of a permutation-based variant of mastermind ⋮ The \((1+1)\) elitist black-box complexity of LeadingOnes ⋮ Reducing the arity in unbiased black-box complexity

Cites Work

• Unnamed Item
• Mastermind
• On the algorithmic complexity of the Mastermind game with black-peg results
• Randomization, derandomization and antirandomization: Three games
• Playing Mastermind With Many Colors
• Searching games with errors -- fifty years of coping with liars