Generic NP-incomplete problems

Rybalov, A

Rybalov, A (reprint author), Omsk State Tech Univ, Prospekt Mira 11, Omsk 644050, Russia.

MECHANICAL SCIENCE AND TECHNOLOGY UPDATE (MSTU-2018), 2018; 1050 ():

Abstract

Ladner in 1975 proved that if P not equal NP then there exist problems in NP, which are not decidable in polynomial time and not NP-complete. Kapovich......

Full Text Link