On Membership Comparable Sets

摘要

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 2k(n) possibilities for the memberships of the given strings in A. We show that if SAT is O(log n) membership comparable, then the NP-hard promise problem UniqueSAT can be solved in polynomial time. Our result settles an open question, suggested by Buhrman, Fortnow, and Torenvliet, and extends the work of Ogihara, Beigel, Kummer, Stephan, and Agrawal and Arvind. 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 UniqueSAT∈DTIME[2log2 n]. Our proof also shows that if SAT is o(n) membership comparable, then UniqueSAT can be solved in deterministic time 2o(n). Our main technical tool is an algorithm of Madhu Sudan (building on the work of Ar, Lipton, Rubinfeld, and Sudan) to reconstruct polynomials from noisy data through the use of bivariate polynomial factorization.