On P-Immunity of Exponential Time Complete Sets

摘要

We show that every many-one complete set for NEXP (co-NEXP) has an infinite subset in P. We also show that every many-one complete set for EXP has anonsparseinfinite subset in P iff annihilating functions do not exist.