Polynomial-time Membership Comparable Sets.
This paper studies a notion called polynomial-time membership comparable sets. For a function $g$, a set $A$ is polynomial-time $g$-membership comparable if there is a polynomial-time computable function $f$ such that for any $x_1, \cdots, x_m$ with $m \geq g(\max\{ |x_1|, \cdots, |x_m| \})$, outputs $b \in \{0,1\}^m$ such that $(A(x_1), \cdots, A(x_m)) \neq b$. The following is a list of major results proven in the paper.  1. Polynomial-time membership comparable sets construct  a proper hierarchy according to the bound on the number  of arguments.  2. Polynomial-time membership comparable sets have  polynomial-size circuits.  3. For any function $f$ and for any constant $c>0$,  if a set is $\leq^p_{f(n)-tt}$-reducible to a P-selective set,  then the set is polynomial-time $(1+c)\log f(n)$-membership  comparable.  4. For any $\cal C$ chosen from $\{ {\rm PSPACE, UP, FewP, NP, C_{=}P, PP, MOD_{2}P, MOD_{3}}, \cdots \}$,  if $\cal C \subseteq {\rm P-mc}(c\log n)$ for some $c<1$,  then $\cal As a corollary of the last two results, it is shown that if there is some constant $c<1$ such that all of $\cal C$ are polynomial-time $n^c$-truth-table reducible to some P-selective sets, then $\cal which resolves a question that has been left open for a long time.
Introduction
Given two strings x and y, can we tell which is more likely to be in a set A? Jockusch [Joc68]
defined a set A to be semirecursive if there is a recursive function f such that for all x and y,
A. We call the function f a selector
for A. Selman [Sel79] considered a polynomial-time analogue of semirecursive sets and
defined a set A to be P-selective if A has a polynomial-time computable selector. P-selective
sets have been widely studied [Sel82b, Sel79, Sel82a, AH92, Ko83, Tod91, LS93, BvHT93,
Recently, there have been some remarkable results
about P-selective sets. Buhrman, van Helden, and Torenvliet [BvHT93] have shown that
a set is in P if and only if it is - p
T -self-reducible and P-selective, while previously known
characterization is A 2 P if and only if A is - p
ptt -self-reducible and P-selective [Sel82b].
Naik et al [NOS93, HNOS93] have proven, by constructing P-selective sets with certain
properties, that NP search problems are not reducible to corresponding decision problems
unless some implausible collapses of exponential-time complexity classes occur. Hemachan-
dra et al [HHO studied internal structure of the class of sets - p
T -reducible to P-selective
sets and introduced the notion of FC-selectivity for various function classes FC. Hemas-
paandra, Naik, Ogiwara, and Selman [HNOS94] have studied sets with nondeterministically
polynomial-time computable selectors, and proven that if there is an NP-function that computes
satisfying assignments uniquely, then the polynomial-time hierarchy [MS72, Sto77],
collapses to its second level \Sigma p
.
For a set A, let us identify A and its characteristic function. For any x and y, there
are four possible values of (A(x); A(y)). By mapping a pair (x; y) to y, a selector for A
declares that "x 2 A ! y 2 A," equivalently, "(A(x); A(y)) 6= (1; 0)." Thus one can view
a selector for A as a function f that maps (x; y) to b 2 f0; 1g 2 such that (A(x); A(y)) 6= b,
where b is always either 01 or 10. An interesting and fundamental question arising from
this observation is "how strong is the restriction b 2 f01; 10g?"; that is, if we allow f to
map to 00 or 11, then "how largely does the complexity of A increase?" Let us consider
this in a more generalized setting and define the notion of polynomial-time membership
comparable sets. Let N denote the set of all nonnegative (positive) integers. Call a
polynomially bounded if there is a polynomial p such that for every
polynomial-time computable if there is a polynomial-time bounded
machine that, on input x, outputs 1 g(jxj) .
be monotone nondecreasing, polynomial-time com-
putable, and polynomially bounded.
1. A function f is called a g-membership comparing function (a g-mc-function, in short)
for A if for every x
2. A set A is polynomial-time g-membership comparable if there exists a polynomial-time
computable g-mc-function for A.
3. P-mc(g) denotes the class of all polynomial-time g-membership comparable sets.
Crucial property of mc-functions is that they exclude one value out of 2 m possible values.
The notion-excluding possible values of (A(x 1 ))-has already appeared in the
literature. For a fixed k - 1, the function that, on input x
has been called F A
notions related to F A
k have been introduced and studied (see
[AG88, ABG90, Bei91, BGGO88]). If one can always reduce 2 k possible values of F A
k to
k is said to be computable by a set of m polynomial-time functions [ABG90]
and said to be m-enumerable [CH89]. A set A is non-p-superterse [Bei91] if for some k - 1,
there is a polynomial-time algorithm that computes F A
using adaptive queries to
some set X . So, for a non-p-superterse set A, F A
k is 2 k\Gamma1 -enumerable for some k - 1.
Polynomial-time membership comparable sets are more general than these notions in the
sense that (i) k can be increased according to the length of the input and that (ii) only one
value is required to be excluded.
Purely as a convention, when a function g with the set of real numbers as its range is
used, we will be identifying g and -n:[maxf1; bg(n)cg]. We use P-mc(const), P-mc(log),
and P-mc(poly) respectively to denote S
and S
is a polynomialg, where log is base 2. It is possible for many different
(indeed, even an uncountable number of) sets to be in P-mc(poly) via the same function g.
See Proposition 4.1 for an example of when this actually happens.
In Section 2, we study basic properties of polynomial-time membership comparable sets.
It is easily observed that the smallest P-mc-class, namely P-mc(1), is equal to P. Noting
that P-Sel, the class of P-selective sets, is a subclass of P-mc(2) and that P ae P-Sel [Sel79],
we have P-mc(1) ae P-mc(2). We show that the inequality holds for arbitrary k; that is,
- 1. More generally, we prove that for any f and
g such that f(n) ! g(n) for finitely many n, P-mc(g) contains a set not in P-mc(f ).
Therefore, P-mc-classes construct a proper hierarchy according to the bound on the number
of arguments.
As P-mc(2)-sets can be viewed as less restrictive P-selective sets, one might expect that
P-mc-sets do not go far beyond P-Sel. In Section 3, we consider the question of how they
are related to each other. We seek to prove inclusions between reducibility classes of P-Sel
and P-mc-classes. For a reducibility - p
r and a class C, let R r (C) denote the class of all
sets that are - p
r -reducible to some set in C. Basically, P-mc(2) properly includes P-Sel:
there is a tally set in P-mc(2) \Gamma P-Sel. Furthermore, we prove for any function f , that
c) log f(n)) for any constant c ? 0, which yields R btt (P-Sel) '
P-mc(const) and R tt (P-Sel) ' P-mc(log).
We also study the question of the other direction, namely, whether P-mc-sets are
polynomial-time reducible to P-selective sets. We show that P-mc(poly) ' P=poly, where
P=poly is the class of all sets having polynomial-size circuits. Then, since R T
P=poly [Ko83], we have P-mc(poly) ' R T (P-Sel). The - p
T -reducibility in this inclusion
is optimal, for, we show R tt (P-Sel) ae P-mc(poly). On the other hand, converse statement
"P=poly ' P-mc(poly)" does not appear to hold. But we can show at least that
the question is very subtle. For, P=poly 6' P-mc(poly) implies P 6= NP. Thus, proving
that P-mc(poly) ae P=poly is at least as hard as proving P 6= NP. We conjecture that the
converse inclusion does not hold.
It is well-known that P=poly = R tt
denotes the class of all sparse (tally) sets. As it holds that P-mc(poly) ' P=poly, every
P-mc-set is - p
tt -reducible to some tally set. In Section 4, we attempt to find close
relationships between P-mc-sets and sparse sets as well as tally sets. We prove that
R 1-tt (SPARSE) ' P-mc(poly), and thus, R tt P=poly. Interestingly, this
contrasts that R tt (P-Sel) ae P=poly [HHO + 93]. In order to study relationships between
P-mc-sets and tally sets, binary real numbers will be useful since the characteristic sequence
of a tally set can be viewed as a binary real number in [0; 1) (see [Sel79]). We show
for any binary real number r 2 [0; 1), that Prefix [r], the set of all prefixes of r, is in P-mc(2),
while there is a binary real number r such that Prefix [r] 62 P-Sel.
We add a few words about relationships between P-mc(poly) and TALLY. Noting that
P=poly and TALLY ' P-mc(poly), we show for every A 2 P-mc(poly), that
there is a tally set T in P-mc(poly)" \Delta p
(A) such that A - p
tt T . On the other hand, any tally
set is - p
T -equivalent to some P-mc(2)-set. Thus, every set A in P-mc(poly) is - p
-reducible
to some set in
3 (A). As a consequence, we have P=poly
P-mc(2)); that is, - p
T -reducibility to sparse sets in P-mc(2) completely characterizes P=poly.
Selman [Sel79] showed that SAT is P-selective if and only if SAT is in P. Can we
prove a similar result for P-mc-sets? We consider this question in Section 5. Noting that
P=poly and that NP ' P=poly implies
([KL80]), one can easily
observe that SAT 2 P-mc(poly) only if
. But we have a stronger collapse for some
P-mc-class. We prove NP ' P-mc(c log n) for some c ! 1 if and only if
The proof technique we develop enables us to resolve some open questions. The first
bonus we get is the following result: If for some constant c ! 1, NP ' R n c -tt (P-Sel), then
NP. It has been one of the most important questions whether NP ' R r (P-Sel) =)
NP holds for a reducibility - p
r [Sel82b, Tod91, HHO extended his first
result to - p
ptt -reducibility by observing that R ptt As for "non-
positive" truth-table reducibilities, there have appeared some observations. Toda [Tod91]
proved that NP ' R tt (P-Sel) implies
al [HHO noticed that NP ' R 1-tt (P-Sel) implies
[TTW94] proved that if NP ' R btt (P-Sel), then NP is in deterministic subexponential-
time. Nonetheless, it has been open for a long time whether NP ' R tt (P-Sel) implies
even whether NP ' R btt (P-Sel) implies NP. We not only give an affirmative
answer to the latter, but improves the upper bound on the number of queries to n c
for any constant c ! 1. We note here that the same result has been independently proven
by Beigel, Kummer, and Stephan [BKS94] and by Agrawal and Arvind [AA94].
Another bonus we get is about complexity of functions that are polynomial-time computable
with access to sets in NP. Krentel [Kre88] showed for any function f(n) - 1log n,
that if FP SAT
(f(n)\Gamma1)-T , then asked whether the same statement
holds for a larger function f . Krentel's proof directly applies to the case f(n) - c log n
for some constant c ! 1. Related to this, Beigel [Bei88] asked a question of whether
(f(n)\Gamma1)-T . For the case f(n) - c log n with c ! 1, Beigel [Bei88] showed for
any - p
1-tt -hard set A for NP, that if FP A
(f(n)\Gamma1)-T for some X , then
Regarding general O(log n) case, Amir, Beigel, and Gasarch [ABG90] showed for
any function O(log n), that if FP SAT
(f(n)\Gamma1)-T
for some X , then \Sigma p
3 .
In this paper, we prove that the conclusion of Beigel's result can be strengthen to
The proof techniques we develop can be applied to complexity classes other than NP. We
prove for any class C chosen from fUP; FewP; C=P; PP; PSPACE;MOD 2
that if C ' P-mc(c log n) for some c ! 1, then
Basic Properties of Polynomial-time Membership Comparable
Sets
In this section, we prove some fundamental properties of polynomial-time membership comparable
sets. The reducibility notions we will use are due to [LLS75]. First we state some
rather trivial properties.
Proposition 2.1 1.
2. For any f and g such that f(n) - g(n) for all but finitely many n,
3. If A - p
is in P-mc(f(n)), then A 2 P-mc(f(p(n))) for some polynomial p.
Especially, for any k - 1, P-mc(k) is closed under - p
-reductions.
Proof [(1)] The statement holds because for any set A, A is in P if and only if A c is
in P if and only if there is a polynomial-time computable function f such that for all x,
and g be as in the hypothesis and let n 0 be such that for all n ? n 0 , f(n) - g(n).
Let A 2 P-mc(f) and let T be the set of all strings in A of length at most n 0 . Let x
and n be such that maxfjx 1 g(n). If there is some i such that
If for every i, jx Therefore, A
is in P-mc(g).
via a machine M and B 2 P-mc(f) via h. Let p be a polynomial
bounding the run-time of M . For each x, let Q(x) denote the unique query of M on x.
be the set of all x such that M on x rejects (accepts) no matter what the
answer from the oracle is. Let R 0 (R 1 ) be the set of all x such that M on x accepts if and
only if Q(x) is not in the oracle (Q(x) is in the oracle). Note that W 0
be such that maxfjx 1
(Case be the smallest i such that x i
(Case
(Subcase 2a) There is some (i; l) be the
smallest such pair. Define h 0
(Subcase 2b) For every
It is easy to observe that h 0 behaves correctly. 2
Proposition 2.1 (2) states that P-mc(f) ' P-mc(g) if for all but finitely many n,
g(n). Interestingly, as we shall show below, P-mc(f) differs from P-mc(g) if for infinitely
many n, We note here that the proof we develop has a flavor similar to that
of [AG88, Theorem 2].
Theorem 2.2 Let f and g be monotone nondecreasing, polynomial-time computable, polynomially
bounded functions that map N to N + . Suppose for infinitely many n, it holds
that g(n) ? f(n). Then there is a set A 2 P-mc(g) n P-mc(f ).
Proof Let f and g as in the hypothesis of the theorem. Since f is polynomially bounded,
there is some n 0 such that for every n - n 0 , . Define a sequence fl i g i-1 as follows:
By our hypothesis, fl i g i-1 is a sequence of integers for which g is larger than f . Let h
be an enumeration of all polynomial-time computable functions such that for each i, h i is
computable in time
We construct A in stages. At stage s, we diagonalize against h s by putting at most f(l s )
string of length l s into A. Note that there are more than f(l s ) strings of length l s because
. The construction at stage s proceeds as follows: For each
be the i-th smallest string of length l s . Let
is already not an f-mc function. So, we proceed to the next stage adding no new elements
to A. If b 2 f0; 1g f(ls ) , then for each i, we put w i into A if and only if the i-th bit of b is
a 1. This yields h s (w cannot be an f-mc function
for A. Clearly, this construction establishes A 62 P-mc(f ).
Next we define a g-mc function fl for A. Let y be such that
loss of generality, we may assume that jy 1
Let - be the largest i such that l i - jy m j. There are the following four possible cases:
(a) For some i, jy Clearly, for any such i, y i 62 A. Define fl(y
(b) For some holds that y
only if y j 2 A. So, let s be the smallest i such that y i appears in y
(c) jy are all distinct: By definition, it holds that
l - has at most f(l - ) elements, some y i is not in A. Define
are all
distinct: We simulate the construction of A at stage s to compute A c (y 1 ) and define
In each case, it holds that fl(y is a g-mc function for A.
It remains to show that fl is polynomial-time computable. Since f and g are both
polynomial-time computable and fl i g i-1 is a strictly increasing sequence, - and l
are computable in time polynomial in jy m j. So, one can easily compute the value of fl for
the cases (a), (b), and (c). Now suppose that the case (d) holds. Since s ! -, it holds
that s - jy 1 j - log log jy m j. Since h s is computable in time polynomially
bounded, for some fixed constant k, the construction at stage s can be simulated in time
can be tested in
Therefore, fl is polynomial-time computable. This proves the theorem. 2
Corollary 2.3 If f(n) ? g(n) for infinitely many n and g(n) ? f(n) for infinitely many n,
then by the above theorem, P-mc(f) and P-mc(g) are incomparable.
Corollary 2.4 P-mc-classes construct a proper hierarchy according to the bound on the
number of arguments; namely,
3 Relationships with P-selective Sets
In this section, we study relationships between polynomial-time membership comparable
sets and P-selective sets. First of all, by definition, P-Sel is a subclass of P-mc(2).
Proposition 3.1 P-Sel ' P-mc(2).
The above inclusion is proper.
Theorem 3.2 There is a tally set T 2
Proof be an enumeration of all polynomial-time computable arity-2 functions.
Let f i be computable in time
and define -(4n). For each i - 1, let . Our set T is constructed in stages.
At stage i, we do the following:
Otherwise, put u 2i into T .
Clearly, for any i, either f i is not a selector function or there exist some x 2 T and y 2 T c
such that either f i (x; y. So, T 62 P-Sel. We need to show that
any i, that the construction up to stage i can be simulated in time
1)). Define a function g as follows: Let
tally strings.
(Case 1) s 6= -(k) for any k: Define g(x;
(Case
(Case
(Subcase Simulate the construction of T up to stage bk=2c to
test whether x 2 T . Define g(x;
(Subcase B) bk=2c ? bl=2c: Simulate the construction of T up to stage bl=2c to test
whether
(Subcase C)
It is easy to see that g witnesses that T 2 P-mc(2). This proves the theorem. 2
Are reducibility classes of P-Sel included in P-mc(poly)? The following theorem answers
the question.
Theorem 3.3 be a monotone nondecreasing function. Let L be - p
reducible to a P-selective set. Then, L c) log f(n)) for any constant c ? 0.
The proof of the theorem is based on Lemma 3.4 below, due to Toda, stating that,
given a P-selective set A and a finite set Q, one can compute a linear order over Q such
that A " Q is the initial segment of the order. Originally, Jockusch ([Joc68]. Attributed to
Appel and McLaughlin.) proved that being semi-recursive is equivalent to being the initial
segment of a recursive linear ordering. Regarding P-selective sets, which are defined as the
polynomial-time analogue of semi-recursive sets, Selman [Sel82b] showed that the initial
segment of a polynomial-time linear order is a P-selective set. Ko [Ko83] showed that being
P-selective is equivalent to being the union of initial segments of polynomial-time preorder.
Lemma 3.4 [Tod91] Let A be P-selective. There is a polynomial-time algorithm that,
given a finite set Q ' \Sigma   , outputs an enumeration y of elements in Q such that
there exists some m; such that A " fy
Now we prove the above theorem.
Proof of Theorem 3.3 Let f and L be as in the hypothesis. Let L - p
f(n)-tt A via a
machine M and let A be P-selective. Let c ? 0 and define c) log f(n)c. Let
be such that jg). For each
denote the set of all queries of M on x i , and let
nondecreasing, k Q i k- f(n), so, for sufficiently large n, it holds that
2:
By Lemma 3.4, we can compute, in time polynomial in P
y2R jyj, and thus, in time
polynomial in jxj, an enumeration y of elements in R such that for some
fy mg. Now for each m;
fy for each accepts and
otherwise. Clearly, there is some m such that for every
there is some v 2 f0; 1g h(n) such that v 6= b m;1 \Delta \Delta \Delta b m;h(n) for any
m. Let v 0 be the smallest such v and define r(x It is easy to see that r
witnesses that A 2 P-mc(h). This proves the theorem. 2
Corollary 3.5 P btt (P-Sel) ' P-mc(const) and P tt (P-Sel) ' P-mc(log).
A function h is said to be polynomially length-bounded if there is a polynomial p such
that for every x, jh(x)j - p(jxj).
Definition 3.6 [KL80] A set L is in P=poly if there exist a polynomially length-bounded
function h and a set A 2 P such that for every x, it holds that
Ko [Ko83] showed that P-selective sets have polynomial-size circuits. Noting for a P-
selective set A, a finite set W , and a string x, that W is partitioned into two sets
such that x 2 A =) W 1 ' A and x 2 A c =) W 2 ' A c , Ko developed a divide-and-conquer
method to find polynomially length-bounded advice. Such a method is, however, hard to
find for P-mc(2)-sets, for, the set W is now partitioned into four sets W 4 such that
A c . Nonetheless, very surprisingly, P-mc(poly)-sets have polynomial-size circuits, which is
stated below.
Theorem 3.7 P-mc(poly) ' P=poly.
The proof of the above theorem is essentially the same as that of [ABG90, Theorem
so we omit the proof here. As a matter of fact, in [ABG90], Amir, Beigel, and Gasarch
showed for any k - 1, that P-mc(k) ' P=poly developing an algorithm to construct an
advice string of length O(kn 2 ) for \Sigma n . Thus, even if k is a function of n that is polynomially
bounded, their construction still works.
It is well-known that P=poly = R tt and that TALLY '
R T (P-Sel) [Sel79]. So, every set in P-mc(poly) is - p
T -reducible to some P-selective set.
Corollary 3.8 P-mc(poly) ' R T (P-Sel).
Since R tt (P-Sel) ' P-mc(log) and P-mc(log) 6= P-mc(poly), the above inclusion is optimal

Corollary 3.9 P-mc(poly) 6' R tt (P-Sel).
The converse of Theorem 3.7 does not appear to hold. The question of whether the
converse holds is very subtle. For, proving P-mc(poly) 6= P=poly is at least as hard as
proving P 6= NP.
Theorem 3.10 If P=poly ' P-mc(poly).
Proof Suppose there is a tally
set T and a polynomial time-bounded deterministic oracle Turing machine M such that
for every x, x 2 L if and only if M T on x accepts. Let p be a polynomial bounding the
run-time of M . Without loss of generality, we may assume for every x and oracle X , that
any query of M X on x is in f0; \Delta \Delta g. Let x be strings of length at most
be an enumeration of all subsets of f0
. Note that evert T i can be represented by a string of length p(n). There
is some such that for every accepts if and only if
accepts. For each
accepts and 0 otherwise. For each
there is some
is some c 2 f0; 1g m such that c 6= c i for any i. Let - c be the smallest such c and define
our supposition that
representation of T i ranges over strings of length p(n), the above -
c can be computed in time
polynomial in n, so g is polynomial-time computable. Therefore, L 2 P-mc(p 1). Hence,
P=poly ' P-mc(poly). 2
We conjecture that P-mc(poly) is a proper subclass of P=poly.
4 Relationships with Sparse and Tally Sets
In this section we study relationships between polynomial-time membership comparable sets
and sparse sets as well as tally sets. Since P=poly Theorem
3.7, it holds that P-mc(poly) ' R tt (SPARSE) and P-mc(poly) ' R tt (TALLY). More-
over, as P=poly = R T (P-Sel) and P-Sel ' P-mc(2), we have SPARSE ' R T (P-mc(poly)).
But, in fact, it holds that SPARSE ' P-mc(poly).
Proposition 4.1 SPARSE ' P-mc(poly).
Proof Let S be a sparse set. There is a polynomial p such that for every n,
\Sigma -n k! p(n). Define g to be a function that, given x
. The function g is polynomial-time computable. For every
cannot happen that x
Thus, it is possible for an uncountable number of sets to be in P-mc(poly) via the same
function g.
By Proposition 2.1 (3), we have the following theorem.
Theorem 4.2 R 1-tt (SPARSE) ' P-mc(poly).
For any tally set T , let r(T \Delta. The string r(T ) can be viewed
as a binary real number. For a binary real number r(T ) 2 [0; 1), define Left-Cut [r] to be
the set of binary strings w smaller than or equal to r(T ) in dictionary order and Prefix [r]
to be the set of all initial bits of r(T ). Selman [Sel79] showed the following.
Theorem 4.3 For any binary real number r(T 1), the following properties hold.
1. Left-Cut [r] is P-selective.
2. Left-Cut [r] - p
ptt T and T - p
3. If Prefix [r] is P-selective, then T 2 P.
4. Prefix [r] - p
How complex is Prefix [r]? We show below that Prefix [r] is polynomial-time 2-
membership comparable.
Theorem 4.4 For any r 2 [0; 1), Prefix[r] is in P-mc(2).
Proof Let r 2 [0; 1). Let x; y be distinct two strings. Then the following properties hold:
ffl If x is a prefix of y, then y
ffl If y is a prefix of x, then x
ffl If x is not a prefix of y and y is not a prefix of x, then at most one of x and y is in
if the first condition is satisfied, 10 if the second condition is satisfied,
and 11 otherwise. Clearly, g witnesses that Prefix[r] 2 P-mc(2). 2
Corollary 4.5 For any tally set T , there is a sparse set S 2 P-mc(2) such that T - p
Since there is a tally set not in P, we have the following corollary.
Corollary 4.6 There is a tally set T such that Prefix [r(T )] is in
It is well-known that for every set A 2 P=poly, there is a tally set
(A) such that
tt T (see for example, [Sch86]). By Proposition 4.1, TALLY ' P-mc(poly). So, we have
the following corollary.
Corollary 4.7 For every A 2 P-mc(poly), there is a tally set T in
such that A - p
Moreover, by Corollary 4.5, for every tally set T , there is a sparse set S 2 P-mc(2) such
that T and S are - p
-equivalent. Therefore, we have the following corollary.
Corollary 4.8 For every A 2 P-mc(poly), there is a sparse set S in
that A - p
S.
As SPARSE ' P-mc(poly), we have the following.
Corollary 4.9 For every sparse set S, there is a sparse set S 0
3 (S) such that
Therefore,
P=poly
5 Polynomial-Time Membership Comparable Hard Sets
In this section, we show for some complexity classes C, that if for some c ! 1, C '
P-mc(c log n), then P. We note here that the author has been recently informed
that some of the results in this section had been independently proven by Agrawal and
Arvind [AA94] and by Beigel, Kummer, and Stephan [BKS94]. We start by considering
NP.
Theorem 5.1 If NP ' P-mc(c log n) for some c ! 1, then
Proof Suppose that NP ' P-mc(c log n) for some c ! 1. Take a as a natural number such
that Consider an NP-complete set SAT. Without loss of generality, we may
assume that
ffl for every formula ', each truth assignment for ' is encoded into a string of length
j'j 1=2a .
Let ' be a formula and Y be a set of prefixes of truth assignments for '. Call Y good for
contains a prefix of a satisfying assignment for '. By our assumption, there is an
encoding '#Y of ' and Y such that if k Y k-
is good for 'g. Obviously, A 2 NP, so, A 2 P-mc(c log n). Let f be an
membership comparing function witnessing this property.
Let ' be a formula with be a set of r
many prefixes of truth assignments for '. Suppose that the sets of truth assignments
represented by these prefixes are disjoint; that is, for any i; j; 1
is not a prefix of y j and y j is not a prefix of y i . For each
the set of all y such that the i-th bit of j's binary representation in
f0; 1g d is a 1; that is, j's representation is of the form b 1 1. Note for any
c log j'#Y
must exclude one possibility of (A('#Y 1
to some so that (A('#Y 1
Suppose that . So, at least one of
d is in A, and thus, at least one of Y is good for '. Therefore, ' is
On the other hand, suppose that b 2 f0; 1g d \Gamma f0 d g. Let t be the number whose binary
representation is We show that if Z is good then Z \Gamma fy t g is good. Assume, by
way of contradiction, that Z is good but Z \Gamma fy t g is not good. Then for every i, '#Y i 2 A
if and only if y t 2 Y i . On the other hand, for every i, y only if the i-th bit
of t, which is b i , is a 1. Therefore, for every i, '#Y i 2 A if and only if b
implies (A('#Y 1 contradicts f 's declaration that
fy t g is good. Moreover, if Z \Gamma fy t g
is good, then since it is a subset of Z, Z is good, too. Therefore, in this case, it holds that
Z is good if and only if Z \Gamma fy t g is good.
Define PRUNE to be a procedure that, given ' and Z as above, (i) computes
outputs 'YES' if b is all 0 and outputs Z \Gamma fy t g otherwise.
Clearly, PRUNE is a polynomial-time procedure and for every ' and Z, it holds that:
ffl if PRUNE outputs 'YES', then ' 2 SAT, and
ffl if PRUNE outputs a set Z 0 , then Z 0 is good if and only if Z is good.
Moreover, when Z consists of truth assignments for ', whether Z is good can be tested in
time polynomial in j'j.
Now consider a decision procedure that, given a formula ', behaves as follows:
(0) Initially, set Z to f-g.
(1) According to k Z k, do the following.
z be the smallest y 2 Z in canonical lexicographic order
and replace z with z0 and z1.
outputs 'YES', then accept '.
Otherwise, replace Z with the output of PRUNE .
(2) If not all y 2 Z are truth assignments for ', then goto (1). Otherwise, accept ' if
and only if Z is good.
It is not hard to see that the procedure is polynomial-time bounded and accepts ' if and
only if ' is satisfiable. Therefore, SAT 2 P. This proves the theorem. 2
Remark 1 We note here that the above proof does not seem to work for the case c - 1,
even if we wish to prove a consequence weaker than ' be of length 2 d . Suppose
we wish to preserve k Z k- 2 H(d) \Gamma 1 for some function H . (Note that
we wish to develop a polynomial-time algorithm.) In order to eliminate one prefix from
Z, we construct subsets Y of Z, each consisting of 2 prefixes. Let t be
the average length of prefixes in Z. Then, '#Y i 's must encode at least 2 d
in average. Thus, for some i, it holds j'#Y ff is a constant
depending only on the size of the encoding alphabet. Now, the number of arguments we
must give to f is at least
c log maxfj'#Y 1
As t cannot be bounded by any constant, we may assume log(2 d\GammaH (d) 1. So, we
need more than cH(d)+ c arguments, but if c - 1, this is impossible, because we have only
H(d) arguments. The same arguments apply for the proof of Theorem 5.5.
Next we consider subclasses of NP; namely, UP and FewP, which are defined by
Valiant [Val76] and Allender [All85], respectively. For a polynomial time-bounded nondeterministic
Turing machine M , let #accM denote the function that maps x to the number
of accepting computation paths of M on input x. A set L is in UP (respectively, FewP) if
there is a polynomial time-bounded nondeterministic Turing machine M witnessing L 2 NP
such that for every x, #accM (x) - 1 (respectively, for every x, #accM (x) - p(jxj) for some
polynomial depending only on M ). By Cook's reduction [Coo71] and padding arguments
(see for example, [BH77]), for any NP-acceptor M and for any a 2 N + , one can construct
a polynomial-time computable function f such that the following conditions are satisfied:
is a set of formulas, and is in
ffl for every x, #accM (x) equals the number of satisfying assignments for f(x); and
ffl for every x, truth assignments for f(x) are of length jf(x)j 1=2a .
define A as in the proof of Theorem 5.1 with S in place of SAT.
Thus, we can use our technique to prove results similar to that of Theorem 5.1 for UP and
FewP.
Theorem 5.2 If UP ' P-mc(c log n) for some c ! 1, then
Theorem 5.3 If FewP ' P-mc(c log n) for some c ! 1, then
Next we consider counting complexity classes C=P and PP, and PSPACE. A set A is
in PP [Gil77, Sim75] (C=P [Wag86, Sim75]) if there exist some machines M and N such
that for every x, x 2 A if and only if #accM (x) - #accN (x) (#accM
Theorem 5.4 Let C be in fPP; C=P; PSPACEg. If C ' P-mc(c log n) for some c ! 1, then
Proof Note that NP is a subset of either C or co-C. Since C and co-C are both contained
in P-mc(c log n), by Theorem 5.1,
2 . Since each of C= P, PP, and
PSPACE has 'one word-decreasing self-reducible' - p
m -complete sets [OL93] and if a 'word-
decreasing self-reducible' set A is in P=poly, then \Sigma p
.
This establishes that
2. A set A is in MOD k P [CH90] if there is some machine M such that for every
if and only if #accM (x) 6j 0 modulo k. The argument for C=P; PP, and PSPACE
cannot be applied to MOD k P, for, it is not known whether NP or coNP is included in
MOD k P. So, we need to develop a direct proof.
Theorem 5.5 Let k - 2. If MOD k P ' P-mc(c log n) for some c ! 1, then MOD k
Proof Let k - 2 and suppose MOD k P ' P-mc(c log n) for some c ! 1. Let a be a natural
number such that c loss of generality, we may assume for any formula
' of propositional logic and any truth assignment y for ', that . For a formula
' and
-('; y) =k fyz : yz is a satisfying assignment for 'g k modulo k.
Note for every ' and y, -(';
lg. It is well-known that L 0 is - p
m -complete for MOD k P and it is
clear that L 0 is - p
-reducible to L 1 . Below, we will show that L 1 is in P. Let ' be
a formula and let Y be a set of pairs (y such that for all
1g. Call Y good for ' if for every
our assumption on the length of formulas and their truth assignments,
there is an encoding '#Y such that if k Y k- j'j=2, then j'#Y
to be the set of all '#Y such that Y is good for '. Since MOD k P is closed under - p
reductions [Her90], and thus, co-MOD k P is closed under - p
ctt -reductions by symmetry, we
have A 2 co-MOD k P. So, by our supposition, A c is in P-mc(c log n). Let f be a function
witnessing this property.
We will show that L 1 2 UP. Let ' be a formula such that
1g be such that for every
1g. Moreover, suppose for every
a prefix of y j and y j is not a prefix of y i . For each l be the set of
all (y such that the l-th bit of i's binary representation in f0; 1g d is a 1; that is, i's
representation is of the form b 1 1. It is easy to see that each Y l contains
exactly r=2 pairs, and thus, that j'#Y l
must be of length d and differ from
Suppose that b 2 0 d . Then there is some l such that '#Y l 2 A c , so Y l is not good for
and thus Z is not good for ' because each Y l is a subset of Z.
On the other hand, suppose that b 2 f0; 1g d \Gamma f0 d g. For each i, let b i denote the i-th
bit of b. Let t be the number whose binary representation is b. We show that Z is good
by way of contradiction, that Z \Gamma f(y
and Z is not good. By definition, for every l, Y l is good if and only if (y
On the other hand, for every l, (y only if the l-th bit of t's binary
representation, which is b l , is a 1. So, for every l, Y l is good if and only if b l = 0.
Thus, contradicts f 's declaration that
Therefore, Z is good if Z \Gamma f(y
if Z is good, then obviously, for any nonempty subset Y of Z, Y is good. Hence, Z is good
if and only if Z \Gamma f(y
Now define PRUNE to be a procedure that, given x and Z as above, computes
outputs 'NO' if the value is all 0 and outputs Z
otherwise. Then the following properties hold:
ffl PRUNE is a polynomial-time procedure;
ffl if PRUNE outputs 'NO', then Z is not good; and
ffl if PRUNE outputs Z 0 , then Z is good if and only if Z 0 is good.
Moreover, if Z consists only of pairs of the form (y; m) with y being a truth assignment for
then whether Z is good can be easily tested. Because Z is good if and only if for every
m) 2 Z, it holds that y is a satisfying assignment for x and
Now define M to be a nondeterministic Turing machine that, on input ('; l), behaves
as follows:
(0) Initially, set Z to f(-; l)g.
(1) According to k Z k, do one of the following.
outputs 'NO,' then reject and
halt. Otherwise, set Z to the output of PRUNE .
l be the smallest in
fy in canonical lexicographic order. Nondeterministically guess
replace (y with two
elements
(2) If there is some (y; m) in Z such that y is not a truth assignment for ', then goto (1).
Otherwise, accept ' if and only if Z is good.
Suppose that M on input ('; l) is at the start of step (1) with Z. Suppose that W is good.
If M is to enter (1a), then Z is replaced with a good one, and if M is to enter (1b), then
clearly, there uniquely exists a guess of (n which Z is substituted with a good one.
On the other hand, suppose that Z is not good. If M is to enter (1a), then M either rejects
or substitutes Z with a one that is not good, and if M is to enter (1b), then for every guess
of (n substitutes Z with a one that is not good. So, if ('; l) is in L 1 , then there
exists a unique path leading to step (2) with a good Z; and if ('; l) 62 L 1 , there is no such
path. Therefore, if ('; l) 2 L 1 , there uniquely exists a path leading to acceptance, and if
('; l) 62 L 1 , then there exist no such paths. This implies L 1 2 UP. So, MOD k P ' UP.
Since UP ' MOD k P, by Theorem 5.2, we have
the theorem. 2
The proof techniques we have developed enable us to resolve some open questions.
Selman [Sel79] showed if NP ' Rm (P-Sel), then NP. It has been studied whether a
similar statement holds for more flexible reducibilities. But, it has been open for a long
time whether NP ' R btt (P-Sel) implies Theorems 3.3 and 5.1, we give an
affirmative answer to this question.
Corollary 5.6 NP ' R btt (P-Sel) implies In fact, NP ' R n c -tt (P-Sel) implies
Theorem 5.1 yields another consequence. For a set A and a function f
let FP A
f(n)-T
f(n)-tt ) denote the class of functions that are polynomial-time computable
with at most f(jxj) adaptive (nonadaptive) queries to A. Krentel [Kre88] showed for any
log n, that FP SAT
f(n)-T ' FP SAT
(f(n)\Gamma1)-T if and only if asked whether
a similar result holds for a larger function f . Beigel [Bei88] strengthened the bound to
c log n for any constant c ! 1. He further asked a similar question with FP SAT
f(n)-tt in place of
f(n)-T and showed for any - p
1-tt -hard set A for NP, for any constant c ! 1, and for any
f such that f(n) - c log n, that if FP A
(f(n)\Gamma1)-T for some X , then
We prove that the conclusion of Beigel's result can be strengthened to
Theorem 5.7 Let f(n) - c log n for some constant c ! 1. Let B be - p
1-tt -hard for NP. If
for some set X it holds that FP B
(f(n)\Gamma1)-T , then
Proof The proof is quite similar to that of Theorem 5.1. Let f , c, B, and X be as in the
hypothesis. Without loss of generality, we may assume that log nc for
some natural number a. Define the notion of 'good' sets, the encoding x#Z, and the set A
as in the proof of Theorem 5.1. For every ' and a set Z of at most j'j \Gamma 1 prefixes of truth
assignments for log n for all n.
Let h be a function that, given ' and a set Z of at most j'j \Gamma 1 prefixes of truth assignments
for are subsets of Z defined in the proof
of Theorem 5.1. Since
f(n)-tt , and thus, h 2 FP B
f(n)-tt . So, by
our supposition, h 2 FP X
(f(n)\Gamma1)-T . Let M be a machine witnessing that h 2 FP X
(f(n)\Gamma1)-T .
For every ' and Z, there are 2 possible outputs of M . Since g(n) ! log n, all such
values can be computed in time polynomial in j'j. Moreover, since there are 2 g(j'j) possible
values of (A('#Y 1 )), we can compute, in time polynomial in j'j, a value
which is not equal to (A('#Y 1 be a function
that, given '#Z, maps to v0 log j'j\Gammag(j'j) . Clearly, h 0 is polynomial-time computable, and
Therefore, as in the proof of Theorem 5.1, we can define a polynomial-time decision
procedure for SAT. This proves the theorem. 2
The above two results can be applied to other complexity classes.
Corollary 5.8 Let C be a class chosen from f PSPACE, UP, FewP, C= P, PP, MOD 2 P,
\Deltag.
1. If C ' R n c -tt (P-Sel) for some c ! 1, then
2. Let H be - p
1-tt -hard for A and f(n) - c log n for some c ! 1. If FP H
(f(n)\Gamma1)-T
for some X , then

Acknowledgment

The author would like to thank Lane Hemaspaandra for useful comments



--R

truth-table reductions to P- selective sets
Some connections between bounded query classes and non-uniform complexity
Polynomial terse sets.
Lower bounds for the low hierarchy.
Invertible functions.

Bounded queries to SAT and the Boolean hierarchy.

On isomorphisms and density of NP and other complete sets.
Approximable sets.

Enumerative counting is hard.
On the power of parity polynomial time.
The complexity of theorem proving procedures.
Computational complexity of probabilistic Turing machines.
Relations among mod-classes


Computing solutions uniquely collapses the polynomial hierarchy.
Semirecursive sets and positive reducibility.
Some connections between nonuniform and uniform complexity classes.
On self-reducibility and weak P-selectivity
The complexity of optimization problems.
--TR

--CTR
Till Tantau, Query complexity of membership comparable sets, Theoretical Computer Science, v.302 n.1-3, p.467-474, 13 June
Richard Beigel , Lane A. Hemaspaandra , Harald Hempel , Jrg Vogel, Optimal series-parallel trade-offs for reducing a function to its own graph, Information and Computation, v.173 n.2, p.123-131, March 15, 2002
Alina Beygelzimer , Mitsunori Ogihara, The enumerability of P collapses P to NC, Theoretical Computer Science, v.345 n.2-3, p.248-259, 22 November 2005
Sebastian Bab , Arfst Nickelsen, One query reducibilities between partial information classes, Theoretical Computer Science, v.345 n.2-3, p.173-189, 22 November 2005
Arfst Nickelsen , Till Tantau, Partial information classes, ACM SIGACT News, v.34 n.1, March
Mitsunori Ogihara , Till Tantau, On the reducibility of sets inside NP to sets with low information content, Journal of Computer and System Sciences, v.69 n.4, p.499-524, December 2004
Piotr Faliszewski , Lane Hemaspaandra, Open questions in the theory of semifeasible computation, ACM SIGACT News, v.37 n.1, March 2006
Amihood Amir , Richard Beigel , William Gasarch, Some connections between bounded query classes and non-uniform complexity, Information and Computation, v.186 n.1, p.104-139, 10 October
polynomial-size circuits;polynomial-time reducibilities;p-selective sets