NP-intermediate problems
If you imagine NP as a country, it is tempting to picture only two regions: the easy lowlands (P, problems we can solve fast) and the forbidding peak (the NP-complete problems, the hardest in NP). NP-intermediate problems are the conjectured 'foothills' in between — problems that are in NP, but are believed to be NEITHER solvable in polynomial time NOR NP-complete. They would be genuinely hard, yet not hard enough to encode all of NP. Their very existence depends on the famous conjecture, and the leading suspects are problems of great practical importance.
Precisely, a problem is NP-intermediate if it lies in NP but is neither in P nor NP-complete. Could such a middle ground be empty? Ladner's theorem (1975) answers: IF P is not equal to NP, then NP-intermediate problems MUST exist — the class NP cannot collapse into just P plus the NP-complete problems; there is provably an infinite hierarchy of intermediate difficulties in between. (Ladner's proof is non-constructive, building an artificial padded problem rather than a natural one.) The conjecture is needed because if P = NP, everything in NP would be in P and there would be no intermediate zone at all. So 'NP-intermediate problems exist' is essentially equivalent to believing P is not NP. The most celebrated NATURAL candidates are INTEGER FACTORING (given a composite number, find a nontrivial factor — its decision form is in NP and in co-NP, which makes NP-completeness unlikely, yet no polynomial algorithm is known) and GRAPH ISOMORPHISM (are two graphs the same up to relabelling vertices? — it resisted both a polynomial algorithm and an NP-completeness proof for decades, and a 2015 quasi-polynomial-time algorithm pushed it tantalisingly close to P without reaching it).
Why care about this middle band? Partly because it is where some of the most useful unsolved problems sit, and partly because their special status is load-bearing for technology. The presumed hardness of factoring is the foundation of RSA cryptography: if factoring were in P, RSA would break overnight; if it were NP-complete, breaking RSA would be as hard as everything in NP — but its likely INTERMEDIATE status is a delicate sweet spot, hard enough to be secure yet structured enough that we are not fully certain. The honest framing: NP-intermediate is a CONJECTURED category. We cannot prove any specific natural problem is intermediate, because doing so would require proving it is not in P (which would settle, or partly settle, P versus NP). So these are best understood as our best guesses about a structure we strongly believe in but have not pinned down — a reminder of how much about computational hardness remains genuinely unknown.
Integer factoring is the poster child. The decision version ('does N have a factor below k?') is in NP (exhibit the factor) AND in co-NP (exhibit the full prime factorisation), and a problem in both is widely believed not to be NP-complete. Yet no polynomial-time factoring algorithm is known on classical computers, so factoring sits, conjecturally, in the NP-intermediate band — exactly the cosy spot RSA relies on.
If P is not NP, intermediate problems must exist (Ladner); factoring and graph isomorphism are top suspects.
We cannot PROVE any natural problem is NP-intermediate — that would require showing it is not in P, partly settling P-vs-NP. Ladner only guarantees SOME intermediate problem exists (if P is not NP), via an artificial construction; factoring and graph isomorphism are conjectures, not theorems.