On membership comparable sets
D. Sivakumar · 2002
A set A is k(n) membership comparable if there is a polynomial time computable function that, given k(n) instances of A of length at most n, excludes one of the 2/sup k(n)/ possibilities for the memberships of the given strings in A. We show that if SAT is O(logn) membership comparable, then UniqueSAT/spl isin/P. This extends the work of previous authors and answers in the affirmative an open question suggested by H. Buhrman et al. (1997). Our proof also shows that if SAT is o(n) membership comparable, then UniqueSATcan be solved in deterministic time 2/sup 0(n)/. Our main technical tool is an algorithm of S. Ar et al. (1992) to reconstruct polynomials from noisy data through the use of bivariate polynomial factorization.