In this chapter we present several interesting results regarding bi-immunity and related notions. We characterize the sets which are bi-immune for P by several different properties. A stronger notion is defined, and a construction of a set having this property is presented. Then it is shown that several properties of polynomial time m-reducibility and of the sets complete for this reducibility can be deduced from the existence of bi-immune sets.