ECCC-Report TR02-004https://eccc.weizmann.ac.il/report/2002/004Comments and Revisions published for TR02-004en-usTue, 08 Jan 2002 23:50:50 +0200
Paper TR02-004
| A Note on the Power of Extra Queries to Membership Comparable Sets |
Till Tantau
https://eccc.weizmann.ac.il/report/2002/004A 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.
Tue, 08 Jan 2002 23:50:50 +0200https://eccc.weizmann.ac.il/report/2002/004