Separation of NP-Completeness Notions.
We use hypotheses of structural complexity theory to separate various NP-completeness notions. In particular, we introduce an hypothesis from which we describe a set in NP that is $\mbox{${\leq}^{\rm P}_{\rm T}$}$-complete but not $\mbox{${\leq}^{\rm P}_{tt}$}$-complete.  We provide fairly thorough analyses of the hypotheses that we introduce.
Introduction
Ladner, Lynch, and Selman [LLS75] were the first to compare the strength of polynomial-time
reducibilities. They showed, for the common polynomial-time reducibilities, Turing
btt ), and many-one
s means that # P
r is properly stronger than # P
s B,
but the converse does not hold. In each case, the verifying sets belong to
Ladner, Lynch, and Selman raised the obvious question of whether reducibilities differ on
NP. If there exist sets A and B in NP (other than the empty set or S # ) such that A# P T B but
A
immediately. With this in mind, they conjectured
that P #= NP implies that # P
m differ on NP.
In the intervening years, many results have explained the behavior of polynomial-time
reducibilities within other complexity classes and have led to a complete understanding
of the completeness notions that these reducibilities induce. For example, Ko and
Moore [KM81] demonstrated the existence of # P
T -complete sets for EXP that are not # P
complete. Watanabe [Wat87] extended this result significantly, showing that # P
btt -,
tt -, and # P
T -completeness for EXP are mutually different, while Homer, Kurtz, and Royer
[KR93] proved that # P m - and # P
1-tt -completeness are identical.
# Department of Computer Science and Engineering, University at Buffalo, Buffalo, NY 14260. Email:
Department of Computer Science and Engineering, University at Buffalo, Buffalo, NY 14260. Email:
selman@cse.buffalo.edu

However, there have been few results comparing reducibilities within NP, and we have
known very little concerning various notions of NP-completeness. It is surprising that
no NP-complete problem has been discovered that requires anything other than many-one
reducibility for proving its completeness. The first result to distinguish reducibilities within
NP is an observation of Wilson in one of Selman's papers on p-selective sets [Sel82].
It is a corollary of results there that if NE# co-NE #= E, then there exist sets A and B
belonging to NP such that A# P
ptt B, B# P
ptt denotes positive truth-table
reducibility. Regarding completeness, Longpr- e and Young [LY90] proved that there
are # P
-complete sets for NP for which # P
T -reductions to these sets are faster, but they did
not prove that the completeness notions differ. The first to give technical evidence that # P
-completeness for NP differ are Lutz and Mayordomo [LM96], who proved that
if the p-measure of NP is not zero, then there exists a # P 3-tt -complete set that is not # P m -
complete. Ambos-Spies and Bentzien [ASB00] extended this result significantly. They
used an hypothesis of resource-bounded category theory that is weaker than that of Lutz
and Mayordomo to separate nearly all NP-completeness notions for the bounded truth-table
reducibilities.
It has remained an open question as to whether we can separate NP-completeness notions
without using hypotheses that involve essentially stochastic concepts. Furthermore,
the only comparisons of reducibilities within NP known to date have been those just listed.
Here we report some exciting new progress on these questions. Our main new result introduces
a strong, but reasonable, hypothesis to prove existence of a # P
T -complete set in NP
that is not # P
tt -complete. Our result is the first to provide evidence that # P tt -completeness
is weaker than # P
-completeness. Let Hypothesis H be the following assertion: There is
a UP-machine M that accepts 0 # such that (i) no polynomial time-bounded Turing machine
correctly computes infinitely many accepting computations of M, and (ii) for some
e > 0, no 2 n e
time-bounded Turing machine correctly computes all accepting computations
of M. Hypothesis H is similar to, but seemingly stronger than, hypotheses considered by
researchers previously, notably Fenner, Fortnow, Naik, and Rogers [FFNR96], Hemaspaan-
dra, Rothe and Wechsung [HRW97], and Fortnow, Pavan, and Selman [FPS99].
This result is especially interesting because the measure theory and category theory
techniques seem to be successful primarily for the nonadaptive reducibilities. Wewill prove
an elegant characterization of the genericity hypothesis of Ambos-Spies and Bentzien and
compare it with Hypothesis H. Here, somewhat informally, let us say this: The genericity
hypothesis asserts existence of a set L in NP such that no 2 2n time-bounded Turing machine
can correctly predict membership of infinitely many x in L from the initial characteristic
sequence That is, L is almost-everywhere unpredictable within time
2 2n . Clearly such a set L is 2 2n -bi-immune. In contrast, we show that Hypothesis H holds if
there is a set L in UP#co-UP such that L is P-bi-immune and L#0 # is not in DTIME(2 n e
for some e > 0. Thus, we replace "almost-everywhere unpredictable" with P-bi-immunity
and we lower the time bound from 2 2n to 2 n e
, but we require L to belong to UP# co-UP
rather than NP.
We prove several other separations as well, and some with significantly weaker hy-
potheses. For example, we prove that NP contains # P
T -complete sets that are not # P m -
complete, if NP# co-NP contains a set that is 2 n e
-bi-immune, for some e > 0.
Preliminaries
We use standard notation for polynomial-time reductions [LLS75], and we assume that
readers are familiar with Turing, # P
T , and many-one, # P
reducibilities. A set A is truth-table
reducible to a set B (in symbols A # P tt B) if there exist polynomial-time computable
functions g and h such that on input x, g(x) is a set of queries Q= {q 1 , q 2 , - , q k }, and x #A
if and only if h(x,B(q 1 1. The function g is the truth-table generator
and h is the truth-table evaluator. For a constant k > 0, A is k-truth-table reducible to B
k-tt B) if for all x, and A is bounded-truth-table reducible to B (A# P
there is a constant k > 0 such that A # P
k-tt B. Given a polynomial-time reducibility # P r ,
recall that a set S is # P r -complete for NP if S # NP and every set in NP is # P r -reducible to
S.
Recall that a set L is p-selective if there exists a polynomial-time computable function
such that for all x and y, f (x,y) # {x,y} and f (x,y) belongs to L, if either
x # L or y # L [Sel79]. The function f is called a selector for L.
Given a finite alphabet, let S w denote the set of all strings of infinite length of order
type w. For r # S #S w , the standard left cut of r [Sel79, Sel82] is the set
where < is the ordinary dictionary ordering of strings with 0 less than 1. It is obvious that
every standard left cut is p-selective with selector f (x,y) =min(x,y).
Given a p-selective set L such that the function f defined by f
selector for L, we call f a min-selector for L. We will use the following simplified version
of a lemma of Toda [Tod91].
be a p-selective set with a min-selector f . For any finite set Q there exists
a string z # Q#} such that z}. The
string z is called a "pivot" string.
Now we review various notions related to almost-everywhere hardness. A language
L is immune to a complexity class C , or C -immune, if L is infinite and no infinite subset
of L belongs to C . A language L is bi-immune to a complexity class C , or C -bi-immune,
if L is infinite, no infinite subset of L belongs to C , and no infinite subset of L belongs
to C . A language is DTIME(T (n))-complex if L does not belong to DTIME(T (n)) almost
everywhere; that is, every Turing machine M that accepts L runs in time greater than T (|x|),
for all but finitely many words x. Balc- azar and Sch- oning [BS85] proved that for every
time-constructible function T , L is DTIME(T (n))-complex if and only if L is bi-immune
to DTIME(T (n)).

Given a time bound T (n), a language L is T (n)-printable if there exists a T (n) time-bounded
Turing machine that, on input 0 n , prints all elements of L#S =n [HY84]. A set S
is T (n)-printable-immune if S is infinite and no infinite subset of S is T (n)-printable.
In order to compare our hypotheses with the genericity hypothesis we describe time-bounded
genericity [ASFH87]. For this purpose, we follow the exposition of Ambos-Spies,
Neis, and Terwijn [ASNT96]. Given a set A and string x,
is the n-th string in lexicographic order. We identify the initial
segment A|z n with its characteristic sequence; i.e., A|z n =A(z condition is a
set C # S # . A meets C if for some x, the characteristic sequence A|x #C. C is dense along A
if for infinitely many strings x there exists i # {0,1} such that the concatenation (A|x)i #C.
Then, the set A is DTIME(t(n))-generic if A meets every condition C#DTIME(t(n)) that is
dense along A. To simplify the notation, we say that A is t(n)-generic if it is DTIME(t(n))-
generic.
Finally, we briefly describe the Kolmogorov complexity of a finite string. Later we will
use this in an oracle construction. The interested reader should refer to Li and Vit- anyi [LV97]
for an in-depth study. Fix a universal Turing machine U . Given a string x and a finite set
the Kolmogorov complexity of x with respect to S is defined by
0, then K(x|S) is called the Kolmogorov complexity of x, denoted K(x). We will use
time-bounded Kolmogorov complexity K t (x) also. For this definition, we require that U(p)
runs in at most t(|x|) steps.
3 Separation Results
Let Hypothesis H be the following assertion:
Hypothesis H: There is a UP-machine M that accepts 0 # such that
1. no polynomial time-bounded Turing machine correctly computes infinitely many accepting
computations of M, and
2. for some e > 0, no 2 n e
time-bounded Turing machine correctly computes all accepting
computations of M.
Theorem 1 If Hypothesis H is true, then there exists a # P
-complete language for NP that
is not # P tt -complete for NP.
Proof. Let M be a UP-machine that satisfies the conditions of Hypothesis H. For each
a n be the unique accepting computation of M on 0 n , and let l |. Define the
language

Define the infinite string a = a 1 a 2 ., and define
to be the standard left-cut of a.
We define to be the disjoint union of L 1 and L 2 . We will prove that L is
T -complete for NP but not # P
T -complete for NP.
Proof. It is clear that L belongs to NP. The following reduction witnesses that SAT# P
Given an input string x, where use a binary search algorithm that queries L 2 to find
a n . Then, note that x # SAT if and only if #x,a n # belongs to L 1 .
Lemma 3 L is not # P
tt -complete for NP.
Proof. Assume that L is # P
tt -complete for NP. Define the set
| the i-th bit of a
Clearly, S belongs to NP. Thus, by our assumption, there is a # P tt -reduction #g,h# from S to
L. Given this reduction, we will derive a contradiction to Hypothesis H.
Consider the following procedure A :
1. input
2. compute the sets Q
3. Let Q 1 be the set of all queries in Q to L 1 and let Q 2 be the set of all queries in Q to
4. If Q 1 contains a query #x,a t #, where t # n e , then output "Unsuccessful" and Print a t ,
else output "Successful".
Observe that this procedure runs in polynomial time. We treat two cases, namely, either
A (0 n ) is unsuccessful, for infinitely many n, or it is successful, for all but finitely many n.
If the procedure A (0 n ) is unsuccessful for infinitely many n, then there is a polynomial
time-bounded Turing machine that correctly computes infinitely many accepting
computations of M, thereby contradicting Clause 1 of Hypothesis H.
Proof. If A (0 n ) is unsuccessful, then it outputs a string a t such that t # n e . Hence, if
A (0 n ) is unsuccessful for infinitely many n, then for infinitely many t there exists an n,
outputs a t . The following procedure uses this observation to
compute infinitely many accepting computations of M in polynomial time.

do
if A (0 j ) outputs a t
then output a t and halt.
The procedure runs in polynomial time because the procedure A (0 j ) runs in polynomial
time.
but finitely many n, then there is a 2 n e
time-bounded
Turing machine that correctly computes all accepting computations of M, thereby contradicting
Clause 2 of Hypothesis H.
Proof. We will demonstrate a procedure B such that for each n, if A (0 n ) is successful,
then B on input 0 n outputs the accepting computation of M on 0 n in 2 n e
time.
If A (0 n ) is successful, then no member of the set Q 1 is of the form #x,a t # where t # n e .
We begin our task with the following procedure C that for each query
decides whether q # L 1 .
1. input
2. If z #= a t for some t, then #y, z# does not belong to L 1 ; (This can be determined in
polynomial time.)
3. if z = a t , where t # n e , then #y, z# belongs to L 1 only if belongs to SAT.
(Since t # n e this step can be done in time 2 n e
Thus, C decides membership in L 1 for all queries q in Q 1 . Therefore, if for each query
q in Q 2 , we can decide whether q belongs to L 2 , then the evaluator h can determine whether
each input #0 n , belongs to S. That is, if for each query q in Q 2 , we can decide
whether q belongs to L 2 , then we can compute a n . We can accomplish this using a standard
proof technique for p-selective sets [HNOS96, Tod91]. Namely, since L 2 is a standard left-
cut, by Lemma 1, there exists a pivot string z in Q 2 #} such that Q 2 #L 2 is the set of
all strings in Q 2 that are less than or equal to z. We do not know which string is the pivot
string, but there are only #Q 2 # choices, which is a polynomial number of choices. Thus,
procedure B on input 0 n proceeds as follows to compute a n : For each possible choice of
pivot and the output from procedure C , the evaluator h computes a possible value for each
j-th bit of a n . There are only a polynomial number of possible choices of a n , because there
are only a polynomial number of pivots. B verifies which choice is the correct accepting
computation of M on 0 n , and outputs that value. Finally, we have only to note that the entire
process can be carried out in 2 n e
steps. This completes the proof of our claim, and of the
theorem as well.

Let Hypothesis H # be the following assertion:
There is an NP-machine M that accepts 0 # such that for some 0 < e < 1,
no
time-bounded Turing machine correctly computes infinitely-many accepting computations
of M.
Theorem 2 If Hypothesis H # is true, then there exists a Turing complete language for NP
that is not # P m -complete for NP.
Proof. Let M be an NP-machine that satisfies the conditions of Hypothesis H # . For each
a n be the lexicographically maximum accepting computation of M on 0 n , and let
. Define the language
an accepting computation
of M on 0 m ,
Let a = a 1 a 2 a 3 -, and define
It is easy to see, as in the previous argument, that L is # P
T -complete for NP. In order to
prove that L is not # P m -complete, we define the set
| y is a prefix of an accepting computation of M on 0 n
which belongs to NP, and assume there is a # P m -reduction f from S to L. Consider the
procedure D in Figure 1: First we will analyze the running time and then we treat two
cases, namely, either D (0 n ) is successful for infinitely many n, or it is unsuccessful for all
but finitely many n.
3 The above procedure halts in O(l n 2 n e 2 /2 ) steps.
Proof. Consider an iteration of the repeat loop. The most expensive step is the test of
whether "z # SAT". This test occurs only when Hence we can decide
whether z belongs to SAT in 2 n e 2 /2 steps. All other steps take polynomial time. Hence the
time taken by the procedure is O(l
the running time of procedure D is bounded by 2 n e
for infinitely many n, then there is a 2 n e
-time-bounded Turing
machine that correctly computes infinitely many accepting computations of M.

input
Repeat l n times
begin
if both x 0 and x 1 are queries to L 2
then if x 0 # x 1
then y := y0
else y := y1
else {At least one of x 0 and x 1 is a query to L 1 {0,1} be the least index
such that x b queries L 1 , and let x
if u is not an accepting computation of M {thus, x b /
then
else {u is an accepting computation of M on 0 t
then output "Unsuccessful," print u, and terminate
else {t < n e
then y := yb
else {x b /
output "Successful" and print y.

Figure

1: Procedure D

Proof. We demonstrate that if D is successful on an input 0 n , then the string that is
printed is an accepting computation of M on 0 n . In order to accomplish this, we prove by
induction that y is a prefix of an accepting computation of M on 0 n during every iteration
of the repeat loop (i.e., a loop invariant). Initially when l this is true. Assume that y is
a prefix of an accepting computation of M at the beginning of an iteration. Then, at least
one of f (#0 n , must belong to L. If both x 0 and x 1 are queries
to L 2 , then the smaller of x 0 and x 1 belongs to L 2 because L 2 is p-selective. Thus, in this
case, the procedure extends y correctly. If at least one of x 0 and x 1 is a query to L 1 , then
the procedure determines whether x b # L 1 , where x b is the query to L 1 with least index. If
x b belongs to L, then #0 n , yb# S. Hence, yb is a prefix of an accepting computation. If
# L, then x -
b belongs to L, because at least one of x b or x - b belongs to L. Thus, in this
case, y -
b is a prefix of an accepting computation. This completes the induction argument.
The loop repeats l n times. Therefore, the final value of y, which is the string that D
prints, is an accepting computation.
but finitely many n, then there is a 2 n e
-time-
bounded Turing machine that correctly computes infinitely many accepting computations
of M.
Proof. The proof is similar to the proof of Claim 1. The following procedure computes
infinitely many accepting computations of M.
input
do
if D (0 j ) outputs u and u is an accepting computation of M on 0 n
then print u and terminate.
The running time of this algorithm can be bounded as follows: The procedure D (0 j )
runs in time l steps. So the total running time is - n 1/e
Since the cases treated both by Claims 4 and 5 demonstrate Turing machines that correctly
compute infinitely many accepting computations of M in 2 n e
time, we have a contradiction
to Hypothesis H # . Thus L is not # P
m -complete for NP.
The following results give fine separations of polynomial time reducibilities in NP from
significantly weaker hypotheses. Moreover, they follow readily from results in the literature


Theorem 3 If there is a tally language in UP-P, then there exist two languages L 1 and
in NP such that L 1 # P tt
Proof. Let L be a tally language in UP-P. Let R be the polynomial-time computable
relation associated with the language L. Define
and
i-th bit of w is one}.
It is clear that L 1 is # P tt -reducible to L 2 . To see that L 2 is # P
T -reducible to L 1 , implement
a binary search algorithm that accesses L 1 to determine the unique witness w such that
then find the i-th bit.
Observe that L 2 is a sparse set. Ogihara and Watanabe [OW91] call L 1 the left set of L,
and they and Homer and Longpr- e [HL94] proved for every L in NP that if the left set of L
btt -reducible to a sparse set, then L is in P. Hence L 1 # btt L 2 .
We now prove that Turing and truth-table reducibilities also differ in NP under the same
hypothesis.
Theorem 4 If there is a tally language in UP-P, then there exist two languages L 1 and
in NP such that L 1 # P
Proof. Hemaspaandra et al. [HNOS96] proved that the hypothesis implies existence
of a tally language L in UP-P such that L is not # P tt -reducible to any p-selective set. In
the same paper they also showed, given a tally language L in NP-P, how to obtain a p-
selective set S such that L is # P
T -reducible to S. Combing the two results we obtain the
theorem.
4 Analysis of the Hypotheses
This section contains a number of results that help us to understand the strength of Hypotheses
H and H # .
1 The class of all languages that are # P
T -equivalent to L 1 is a noncollapsing degree.
4.1 Comparisons With Other Complexity-Theoretic Assertions
We begin with some equivalent formulations of these hypotheses, and then relate them to
other complexity-theoretic assertions. The question of whether P contains a P-printable-
immune set was studied by Allender and Rubinstein [AR88], and the equivalence of items 1
and 3 in the following theorem is similar to results of Hemaspaandra, Rothe, and Wechsung
[HRW97] and Fortnow, Pavan, and Selman [FPS99]. The second item is similar to the the
characterization of Grollmann and Selman [GS88] of one-one, one-way functions with the
addition of the attribute almost-always one-way of Fortnow, Pavan, and Selman.
Theorem 5 The following statements are equivalent:
1. There is a language L in P that contains exactly one string of every length such that
L is P-printable-immune and, for some e > 0, L is not 2 n e
-printable.
2. There exists a polynomial-bounded, one-one, function , such that f is
almost-everywhere not computable in polynomial time, for some e > 0, f is not computable
in time 2 n e
, and the graph of f belongs to P.
3. Hypothesis H is true for some e > 0.
Proof. Let L satisfy item one. Define
the unique string of length n that belongs to L.
Clearly, f us polynomial-bounded and one-one. The graph of f belongs to P, because L
belongs to P. Suppose that M is a Turing machine that computes f and that runs in polynomial
time on infinitely many inputs. Then, on these inputs, M prints L#S n . Similarly, f is
not computable in time 2 n e
Let f satisfy item two. Define a UP-machine M to accept 0 # as follows: On input 0 n ,
M guesses a string y of length within the polynomial-bound of f , and accepts if and only if
The rest of the proof is clear.
Let M be a UP-machine that satisfies item three, i.e., that satisfies the conditions of
Hypothesis H. Let a n be the unique accepting computation of M on 0 n and let |a n
r n be the rank of a n among all strings of length n l . Now, we define L as follows: Given a
string x, if belongs to L if and only if x = a n . If (n-1) l < |x| < n l ,
then x belongs to L if and only if the rank of x (among all the string of length |x|) is r n-1 . It
is clear that L # P and has exactly one string per each length. We claim that L is P-printable-
immune and is not 2 n r
-printable, where machine that prints infinitely many
strings of L in polynomial time can be used to print infinitely many accepting computations
of M in polynomial time. Thus L is P-printable-immune. Any machine that prints all the
strings of L in 2 n r
time can be used print all the accepting computations of M in 2 n e
time.
Thus L is not 2 n r
-printable.
We prove the following theorem similarly.

Theorem 6 The following statements are equivalent
1. There is a language L in P that contains at least one string of every length such that,
for some e > 0, L is 2 n e
-printable-immune.
2. There is polynomial-bounded, multivalued function such that every refinement
of f is almost-everywhere not computable in 2 n e
-time, and the graph of f
belongs to P.
3. Hypothesis H # holds for some e > 0.
Next we compare our hypotheses with the following complexity-theoretic assertions:
1. For some e > 0, there is a P-bi-immune language L in UP#co-UP such that L#0 # is
not in DTIME(2 n e
2. For some e > 0, there is language L in UP#co-UP such that L is not in DTIME(2 n e
3. For some e > 0, there is a 2 n e
-bi-immune language in NP# co-NP.
Theorem 7 Assertion 1 implies Hypothesis H and Hypothesis H implies Assertion 2.
Proof. Let L be a language in UP# co-UP that satisfies Assertion 1. Define M to be the
UP-machine that accepts 0 # as follows: On input 0 n , nondeterministically guess a string
If w either witnesses that 0 n is in L or witnesses that 0 n is in L, then accept 0 n . It is
immediate that M satisfies the conditions of Hypothesis H.
To prove the second implication, let M a UP-machine that satisfies the conditions of
Hypothesis H. Let a n denote the unique accepting computation of M on 0 n and define
It is clear that L # UP#co-UP. If L # DTIME(2 n e
then a binary search algorithm can
correctly compute a n , for every n, in time 2 n e
. This would contradict Hypothesis H. Hence,
The discrete logarithm problem is an interesting possible witness for Assertion 2. The
best known deterministic algorithm requires time greater than 2
3 [Gor93]. Thus, the
discrete logarithm problem is a candidate witness for the noninclusion UP # co-UP #
3 .
Corollary 1 If, for some e > 0, UP # co-UP has a 2 n e
-bi-immune language, then # P
completeness is different from # P tt -completeness for NP.
Theorem 8 Assertion (3) implies Hypothesis H # .
Corollary 2 If, for some e > 0, NP # co-NP has a 2 n e
-bi-immune language, then # P
completeness is different from # P m -completeness for NP.
4.2 Comparisons with Genericity
The genericity hypothesis of Ambos-Spies and Bentzien [ASB00], which they used successfully
to separate NP-completeness notions for the bounded-truth-table reducibilities,
states that "NP contains an n 2 -generic language". Our next result enables us to compare
this with our hypotheses.
We say that a deterministic oracle Turing machine M is a predictor for a language L
if for every input word x, M decides whether x # L with oracle L|x. L is predictable in
time t(n) if there is a t(n) time-bounded predictor for L. We define a set L to be almost-everywhere
unpredictable in time t(n) if every predictor for L requires more than t(n) time
for all but finitely many x. This concept obviously implies DTIME(t(n))-complex almost
everywhere, but the converse does not hold:
Theorem 9 EXP contains languages that are DTIME(2 n )-complex but not almost-everywhere
unpredictable in time 2 n .
Now we state our characterization of t(n)-genericity.
Theorem 10 Let t(n) be a polynomial. A decidable language L is t(n)-generic if and only
if it is almost-everywhere unpredictable in time t(2 n
-1).
Proof. Assume that L is not almost-everywhere unpredictable in time t(2 n
-1), and let
M be a predictor for L that for infinitely many strings x runs in time t(2 n
1). Define a
condition C so that the characteristic sequence
(L|x)x #C #M with oracle L|x runs in time t(2 |x| -1) on input x.
accepts x). Then, C is dense along L because M correctly predicts
whether x # L for infinitely many x. It is easy to see that C # DTIME(t(n)). However, L is
not t(n)-generic because we defined C so that L does not meet C.
Assume that L is not t(n)-generic, and let C #DTIME(t(n)) be a condition that is dense
along L such that L does not meet C. Let T be a deterministic Turing machine that halts on
all inputs and accepts L. Define a predictor M for L to behave as follows on input x with
oracle A|x: If (A|x)1 #C, then M rejects x, and if (A|x)0 #C, then M accepts x. If neither
holds, then M determines membership in L by simulating T on x. Since L does not meet C,
M is a predictor for L. Since C is dense along L and L does not meet C, for infinitely many
x, either (A|x)1 #C or (A|x)0 #C, and in each of these cases, M runs for at most t(2 - 2 |x| )
steps. Since t(n) is polynomial function, by the linear speedup theorem [HS65], there is a
Turing machine that is equivalent to M that runs in time t(2 |x| -1).
Corollary 1 NP contains an n 2 -generic language if and only if NP contains a set that is
almost-everywhere unpredictable in time 2 2n .

By Theorem 8, Hypothesis H # holds if NP# co-NP contains a set that, for some e > 0,
is
-bi-immune. So, Hypothesis H # requires bi-immunity, which is weaker than almost-everywhere
unpredictability, and the time-bound is reduced from 2 2n to 2 n e
. On the other
hand, we require the language to belong to NP# co-NP instead of NP. Similarly, when we
consider Hypothesis H, we require the language to be P-bi-immune and not in DTIME(2 n e ),
whereas now we require the language to be in UP# co-UP. Moreover, the conclusion
of Theorem 1 is not known to follow from the genericity hypothesis. At the same time,
we note that the genericity hypothesis separates several bounded-truth-table completeness
notions in NP that do not seem obtainable from our hypotheses.
4.3 Relativization
Theorem 11 There exists an oracle relative to which the polynomial hierarchy is infinite
and Hypotheses H and H # both hold.
Proof. Define Kolmogorov random strings r 0 , r 1 , . as follows: r n is the first string of
length n such that
Then, define the oracle
Define M to be an oracle Turing machine that accept 0 # with oracle A as follows: On
input guess a string y of length n. If y # A, then accept. M is a UP A -machine that accepts
contains exactly one string of every length.
Now we show that no 2 n e
oracle Turing machine with oracle A, for any 0 < e < 1,
correctly computes infinitely many accepting computations of M. Observe that relative to
A, this implies both Hypotheses H and H # . Suppose otherwise, and let T be such an oracle
Turing machine. The gist of the remainder of the proof is that we will show how to simulate
T without using the oracle, and that will contradict the randomness or r n .
Suppose that T A (0 n . Then we simulate this computation without
using an oracle as follows:
1. Compute . Do this iteratively: Compute r i by running every program
(with input strings r 0 , r 1 , . , r i-1 ) of length # i/2 for 2 i steps. Then r i is the first
string of length i that is not output by any of these programs. Note that the total time
for executing this step is
2. Simulate T on input 0 n , except replace all oracle queries q by the following rules: If
|q| < l, answer using the previous computations. Otherwise, just answer "no."
If the simulation is correct, then this procedure outputs r n without using the oracle. The
running time of this procedure on input 0 n is 2 5n e +2 n e
, which is less than 2 n . So, we can
describe r n by a string of length O(logn), to wit, a description of T and 0 n . This contradicts
the definition of r n .
We need to show that the simulation is correct. The simulation can only be incorrect
if |q| # l and be the first such query. This yields a short
description of r m , given r 0 , r 1 , . , r l-1 . Namely, the description consists of the description
of T (a constant), the description of 0 n (logn bits), and the description of the number j such
that is the j-th query (at most n e ). Thus, the length of the description is O(n e ). Since
that the length of the description of r m is less than m/2. The running
time of T , given r 0 , r 1 , . , r l-1 , is 2 n e
, which is less than 2 m . (The reason is that the first
step in the simulation of T is not needed.) Therefore, the simulation is correct.
Finally, because A is a sparse set, using results of Balc- azar et al. [BBS86], there is an
oracle relative to which the hypotheses holds and the polynomial hierarchy is infinite.
Hypothesis H fails relative to any oracle for which
and Rogers [FR94] obtained an oracle relative to which NP #= co-NP and Hypothesis H #
fails. We know of no oracle relative to which P #= NP and every # P
T -complete set is #
complete.
4.4 Extensions
The extensions in this section are independently observed by Regan and Watanabe [RW01].
In Hypothesis H we can replace the UP-machine by an NP-machine under a stronger intractability
assumption. Consider the following hypothesis:
There is a NP-machine M that accepts 0 # such that
1. no probabilistic polynomial time-bounded Turing machine correctly outputs infinitely
many accepting computations with non-trivial (inverse polynomial) probability, and
2. for some e > 0, no 2 n e
time-bounded Turing machine correctly computes all accepting
computations with non-trivial probability.
We can prove that Turing completeness is different from truth-table completeness in
NP under the above hypothesis. The proof uses the randomized reduction of Valiant and
that isolates the accepting computations. We define L as in the proof of
Theorem 2. Let
i#v such that v is an accepting computation of M,
and the ith bit of
where v.r i denotes the inner product over GF[2].
Valiant and Vazirani showed that if we randomly pick r 1 , r 2 , - , r k , then with a non-trivial
probability there exists exactly one accepting computation v of M whose inner product
with each r i is 0. Thus, for a random choice of r 1 , - , r k , there is exactly one witness v
for i#. The rest of the proof is similar to that of Theorem 1.
We also note that we can replace the UP-machine in Hypothesis H with a FewP-
machine.



--R


Separating NP-completeness under strong hypotheses
Diagonalizations over polynomial time computable sets.
Genericity and measure for exponential time.
Resource bounded randomness and weakly complete problems.
Relativizations of the P


Completeness notions for nondeterministic complexity classes.
On inverting onto functions.
Distributionally hard languages.

Discrete logarithms in GF(p) using the number field sieve.
Complexity measures for public-key cryptosys- tems

Easy sets and hard certificate schemes.
On the computational complexity of algorithms.
Computation times of NP sets of different densities.


Completeness, approximation and density.
A comparison of polynomial time re- ducibilities


Cook versus karp-levin: Separating completeness notions if NP is not small
On polynomial time bounded truth-table reducibility of NP sets to sparse sets
Personal communication.

Reductions on NP and P-selective sets
On polynomial-time truth-table reducibilities of intractable sets to P-selective sets
NP is as easy as detecting unique solutions.
A comparison of polynomial time completeness notions.
--TR

--CTR
A. Pavan , Alan L. Selman, Bi-immunity separates strong NP-completeness notions, Information and Computation, v.188 n.1, p.116-126, 10 January 2004
John M. Hitchcock , A. Pavan, Comparing reductions to NP-complete sets, Information and Computation, v.205 n.5, p.694-706, May, 2007
Christian Glaer , Alan L. Selman , Samik Sengupta, Reductions between disjoint NP-pairs, Information and Computation, v.200 n.2, p.247-267, 1 August 2005
Lane A. Hemaspaandra, SIGACT news complexity theory column 40, ACM SIGACT News, v.34 n.2, June
Christian Glaer , Mitsunori Ogihara , A. Pavan , Alan L. Selman , Liyu Zhang, Autoreducibility, mitoticity, and immunity, Journal of Computer and System Sciences, v.73 n.5, p.735-754, August, 2007
p-selectivity;truth-table completeness;turing completeness;p-genericity;many-one completeness