Completeness, Approximation and Density
Ker‐I Ko, D. Moore · SIAM Journal on Computing · 1981
Polynomial time approximations to exponential time computable problems (EXP) are considered from the point of view of structure. Infinitely often speedable and almost everywhere complex problems are studied using the notions of polynomial time productivity and immunity. In particular, the existence of a polynomial time immune set which is not polynomial time approximable at all but which is polynomial time $tt$-complete in EXP is proven. The relationship between completeness and approximability is also studied. It is shown that being polynomial time m-complete in EXP does not provide any control of the probability of erroneous approximations.