On the number of queries necessary to identify a permutation

DOI10.1016/0196-6774(86)90013-1MaRDI QIDQ3768415zbMATH OpenOpenAlexFDO

Authors Shia-Chung Teng, Ker-I Ko

Publication date 1986

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(86)90013-1

zbMATH Keywords

polynomial-time algorithmsearchingminimum number of queries required to identify an unknown permutationsize of the search spacetwo-person query game

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) 2-person games (91A05)

Recommendations

• The query complexity of finding a hidden permutation
• Quantum queries on permutations
• Quantum Queries on Permutations with a Promise
• Improved Approximation Algorithm for the Number of Queries Necessary to Identify a Permutation
• Solving static permutation mastermind using \(O(n \log n)\) queries

Cited in

(20)

• Improved Approximation Algorithm for the Number of Queries Necessary to Identify a Permutation
• On a query algorithm for a divisibility problem
• Query complexity of mastermind variants
• Permutation Property Testing under Different Metrics with Low Query Complexity
• Unshuffling permutations: trivial bijections and compositions
• A quadratic lower bound for topswops
• In Memoriam: Ker-I Ko (1950–2018)
• Solving static permutation mastermind using \(O(n \log n)\) queries
• Bounds for the static permutation mastermind game
• Query complexity of inversion minimization on trees
• Quantum Queries on Permutations with a Promise
• The query complexity of a permutation-based variant of mastermind
• Optimal strategies for the static black-peg AB game with two and three pegs
• The query complexity of finding a hidden permutation
• Quantum queries on permutations
• Strategy optimization for deductive games
• The exact query complexity of yes-no permutation mastermind
• The worst case number of questions in generalized AB game with and without white-peg answers
• On the query complexity of black-peg AB-mastermind
• Some Completeness Results on Decision Trees and Group Testing

This page was built for publication: On the number of queries necessary to identify a permutation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3768415)