__
TR02-004 | 2nd November 2001 00:00
__

#### A Note on the Power of Extra Queries to Membership Comparable Sets

**Abstract:**
A language is called k-membership comparable if there exists a

polynomial-time algorithm that excludes for any k words one of

the 2^k possibilities for their characteristic string.

It is known that all membership comparable languages can be

reduced to some P-selective language with polynomially many

adaptive queries. We show however that for all k there exists a

(k+1)-membership comparable set that is neither truth-table

reducible nor sublinear Turing reducible to any k-membership

comparable set. In particular, for all k > 2 the number of

adaptive queries to P-selective sets necessary to

decide all k-membership comparable sets is \Omega(n) and

O(n^3). As this shows that the truth-table closure of P-sel

is a proper subset of P-mc(log), we get a proof of Sivakumar's

conjecture that O(log)-membership comparability is a more

general notion than truth-table reducibility to P-sel.