Title: Strong Reductions and Immunity for Exponential Time
Published: March 2002
Authors: Marcus Schaefer, Frank Stephan
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.
Full Paper: [postscript, pdf]