Computational Complexity for Selection Problems with Parity-Like Tests (Thesis)

Abstract:

The computational complexity of sorting type problems using pairwise
comparisons has been studied extensively. For example, let $W_k ( n
)$ denote the number of pairwise comparisons needed to find the $k$
largests among $n$ distinct real numbers. It is known that $W_1 ( n )
= n - 1$, $W_2 ( n ) = n - 2 + lceil log n
ceil$ and, for fixed
$k$, $W_k ( n ) = n + ( k - 1 ) lceil log n
ceil + O ( 1 )$. In
this thesis, we study the computational complexity for selection
problems when some more powerful type of queries, namely, the queries
``$xprod:0$' are allowed. We call queries of the type
``$xprod:0$' partiy-like tests. In some problems, using parity-like
tests can significantly reduced the number of queries needed to be
asked to find an answer. For example, $ heta ( n log n )$ queries
are necessary to determine whether $n$ real numbers are distinct if
the queries are restricted to pairwise comparisons. On the other
hand, one query ``$prod_{i
ot= j} (x_i - x_j ) > 0 ?$' is
sufficient to solve the problem. In the thesis, we study the problem
of selecting the $k$ largests of $n$ distinct real numbers. We show
that when queries are restricted to parity-like tests, $n-k+lceil
log((n(n-1)...(n-k+2))
ceil$ queries are necessary to solve the
problem. In other words, the parity-like tests are not much more
powerful than the simple pairwise comparisons in this problem. We
also study the problem of finding the maximum of $n$ numbers using
small number of queries. The result on selecting the $k$ largests
implies $n-1$ parity-like tests are necessary to find the maximum of
$n$ numbers. However, we show that for any fixed $varepsilon>0$,
there is a decision tree algorithm which finds the maximum of $n$
numbers with error probability $