On the number of queries necessary to identify a permutation

DOI10.1016/0196-6774(86)90013-1zbMATH Open0631.68059OpenAlexW2061014674MaRDI QIDQ3768415FDOQ3768415

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

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

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)

Cited In (20)

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

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)