On the topological size of p-m-complete degrees
Marius Zimand · Theoretical Computer Science · 1995
All polynomial many-one degrees are shown to be of second Baire category in the superset topology when witness functions are allowed to run in 2loghn time, for any h. Any improvement of this result for the complete p-m-degrees of RE, EXP or NP implies P ≠ NP or the nonisomorphism of the NP-complete sets.