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.