Uniformly hard languages
โ
Rod Downey; Lance Fortnow
๐
Article
๐
2003
๐
Elsevier Science
๐
English
โ 163 KB
Ladner (J. Assoc. Comput. Mach. 22 (1975) 155) showed that there are no minimal recursive sets under polynomial-time reductions. Given any recursive set A, Ladner constructs a set B such that B strictly reduces to A but B does not lie in P. The set B does have very long sequences of input lengths of