| Abstract: |
This paper investigates the relation between immunity and hardness
in exponential time.
The idea that these concepts are related originated in computability
theory where it led to Post's program, and it has
been continued successfully in complexity theory (Buhrman 1993, Hartmanis, Li
Yesha, 1986, Schaefer, Fenner, 1998).
We study three notions of immunity for exponential time.
An infinite set A is called EXP-immune, if it does not contain an infinite subset
in EXP; EXP-hyperimmune, if for every infinite sparse set B in EXP and
every polynomial p there is an x in B such that {y in B: p-1(|x|)
<= |y| <= p(|x|)} is disjoint from A; STRONGEXP, if the intersection
of A and B is finite for
every sparse set B in EXP. EXP-avoiding sets are always EXP-hyperimmune and
EXP-hyperimmune sets are always EXP-immune but
not vice versa.
We analyze with respect to which polynomial-time reducibilities
these sets can be hard for EXP. EXP-immune sets cannot be
conjunctively hard for EXP although they can be disjunctively hard.
EXP-hyperimmune sets cannot be conjunctively or disjunctively hard
for EXP, but there is a relativized world in which there is an EXP-avoiding set which is hard with respect to
positive truth-table reducibility.
Furthermore, in every relativized world there is some EXP-avoiding set which is Turing-hard for
EXP.
|