Uniformly hard languages

✍ Scribed by Rod Downey; Lance Fortnow

• Book ID: 104325715
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 163 KB
• Volume: 298
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00810-1

✦ Synopsis

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 easily computable instances.

We examine whether Ladner's results hold if we restrict ourselves to "uniformly hard languages" which have no long sequences of easily computable instances. Under a hard to disprove assumption, we show that there exists a minimal recursive uniformly hard set under honest many-one polynomial-time reductions.