Polynomial-Time Membership Comparable Sets
Lists
Only you see this
Abstract
The paper introduces and studies a notion called polynomial-time membership comparable sets, which is a generalization of P-selective sets. For a function g, a set A is called polynomial-time g-membership comparable if there is a polynomial-time computable function f such that for any x/sub 1/,...,x/sub m/ with m/spl ges/g(max{|x/sub 1/|,...,|x/sub m/|}), outputs b/spl isin/{0,1}/sup m/ such that (A(x/sub 1/),...A(x/sub m/))/spl ne/b. It is shown for each C chosen from {PSPACE, UP, FewP, NP, C=P, PP, MOD/sub 2/P, MOD/sub 3/P,...}, that if all of C are polynomial-time c(log n)-membership comparable for some fixed constant c<1, then C=P. As a corollary, it is shown that if there is same constant c<1 such that all of C are polynomial-time n/sup c/-truth-table reducible to some P-selective sets, then C=P, which resolves a question that has been left open for a long time.<
BibTeX
@article{ogihara1995polynomial,
author = {Mitsunori Ogihara},
title = {{Polynomial-Time Membership Comparable Sets}},
journal = {SIAM Journal on Computing},
year = {1995},
url = {https://openreview.net/forum?id=yI1rH9Qu_Awk},
}Loading related content...