A Note on the Power of Extra Queries to Membership Comparable Sets
Till Tantau · Electronic colloquium on computational complexity · 2002
A language is called k-membership comparable if there exists a polynomial-time algorithm that excludes for any k words one of the 2 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 kmembership comparable sets is Ω(n) and O(n). 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.