Showing cs.CCShow all
2 papers · 1 filter
cs.CC2006
On the structure of linear-time reducibility
Philippe Chapdelaine
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 Sc…
cs.CC2006
Lower bounds and complete problems in nondeterministic linear time and sublinear space complexity classes
Philippe Chapdelaine, Etienne Grandjean
Proving lower bounds remains the most difficult of tasks in computational complexity theory. In this paper, we show that whereas most natural NP-complete problems belong to NLIN (l…