On membership comparable sets

A set A is k(n) membership comparable if there is a polynomial-time computa ble function that, given k(n) instances of A of length at most n, excludes one of the 2(k(n)) possibilities for the memberships of the given strings i n A. We show that if SAT is O(log n) membership comparable, then the NP-har d promise problem UniqueSAT can be solved in polynomial time. Our result se ttles an open question, suggested by Buhrman, Fortnow, and Torenvliet, and extends the work of Ogihara, Beigel, Kummer, Stephan. and Agrawal and Arvin d. These authors showed that if SAT is c log n membership comparable for c < 1, then NP = P, and that if SAT is O(log n) membership comparable, then U niqueSAT is an element of DTIME[2(log2n)]. Our proof also shows that if SAT is o(n) membership comparable, then UniqueSAT can be solved in determinist ic time 2(o(n)). Our main technical tool is an algorithm of Madhu Sudan (bu ilding on the work of Ar, Lipton, Rubinfeld, and Sudan) to reconstruct poly nomials from noisy data through the use of bivariate polynomial factorizati on. (C) 1999 Academic Press.