Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR02-004 | 2nd November 2001 00:00

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


Authors: Till Tantau
Publication: 8th January 2002 23:50
Downloads: 1451


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.

ISSN 1433-8092 | Imprint