On the structure of linear-time reducibility
<|reference_start|>On the structure of linear-time reducibility: In 1975, Ladner showed that under the hypothesis that P is not equal to NP, there exists a language which is neither in P, nor NP-complete. This result was latter generalized by Schoning and several authors to various polynomial-time complexity classes. We show here that such results also apply to linear-time reductions on RAMs (resp. Turing machines), and hence allow for separation results in linear-time classes similar to Ladner's ones for polynomial time.<|reference_end|>
@article{chapdelaine2006on,
    title={On the structure of linear-time reducibility},
    author={Philippe Chapdelaine},
    journal={arXiv preprint arXiv:cs/0606080},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0606080},
    primaryClass={cs.CC}
}