Originators: David Hannasch (presented by David Hannasch - REGS 2010)
Definitions: An oracle gives an answer to a particular type of question in constant time. A 3-branch is an oracle that returns one answer chosen from a set of three possible answers. More generally, an a-branch is an oracle that returns one answer chosen from a set of a possible answers.
Background: Sorting and selection problems request information about an unknown linear ordering using a small number of queries to a specified oracle. For inquiries about order, there is only one 2-branch on two arguments. Sorting with a 2-branch on two arguments has been much studied. In REGS this year, sorting with a k!-branch on k arguments has been studied. Because there are n! possible permutations of n items, there is a lower bound of ⌈log3n!⌉ on the number of 3-branch queries needed to sort n items. Similarly, at least ⌈log3n⌉ queries are needed to find the largest among n items.
Problem 1: Find a good algorithm to sort n items using a 3-branch.
Conjecture 2: No 3-branch on three arguments can sort four items in three queries. More generally, for all n, no 3-branch on three arguments can sort n items in ⌈log3n!⌉ queries.
Question 3: Is there a 3-branch on three arguments that can sort n items in O(log3n!) queries? Is there a 3-branch and algorithm that can sort n items in ⌈log3n!⌉ queries? Is there an a-branch and algorithm that can sort n items in ⌈logan!⌉ queries?
Problem 4: Find a good algorithm to select the largest among n items using a 3-branch.
Comments: The coin-weighing problem, a type of find-the-max problem in which one element is heavier and the others have equal weight, can be solved in ⌈log3 n⌉ queries by a 3-branch that allows many arguments. No oracle that accepts only k arguments can find the largest among n items in ⌈logkn⌉ queries for all n, because at least (n-1)/(k-1) queries are needed to ensure getting the two largest elements in the same ``component'' of comparisons.
There is an a-branch oracle due to Dan McDonald that can find the maximum in ⌈loga n⌉ queries: a plates that can hold any number of items are enchanted so that the plate with the largest single item on it lights up. For a find-the-outlier problem like the coin-weighing problem, this can be interpreted as a generalized scale. If the weight of the outlier is greater than the total weight of the next n/a heaviest elements minus the total weight of the n/a - 1 smallest elements, then the plate with the outlier will always have the greatest total weight. An a-way scale might be constructed by floating a board with a pegs in a holes on water; the peg that sinks lowest has the greatest total weight and therefore holds the outlier.