2006/06/19 by Philippe Chapdelaine, Chapdelaine, Philippe
Computer Science · Engineering · Mathematics · #Advanced Control Systems Optimization #Advanced Optimization Algorithms Research #Computational Complexity (cs.CC) #F.1.3 #F.4.1 #FOS: Computer and information sciences #Polynomial and algebraic computation #cs.CC
paper · pdf · doi:10.48550/arxiv.cs/0606080
10 pages
arxiv created 2006/06/19 · openalex publication_date 2006/06/19 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.