Motivated by my post, Is there a program for theory of incompleteness in NP, much of NP-completeness theory has been heavily influenced by computability theory for which we were successful in proving the existence of incomplete sets in R.E. using diagonalization method.

Reductions in complexity theory are the resource bounded versions of many-one and Turing reductions of computability theory. Also, the standard notion of efficient algorithms is the resource bounded version of Turing machines. Completeness is defined using Karp reduction (polynomial time many-one reduction).

Although that served us very well into classifying problems into intractable NP-complete problems and efficiently solvable ones, the analogue breaks down when it comes to natural incomplete problems inside R.E. and NP.

As far as I know, there are no known natural intermediate (incomplete) problems between R.E. degree and Recursive degree. We were only able to prove the existence of artificial problems with intermediate degrees. In contrast in complexity theory, we have plenty of intermediate problems. This post, Techniques for showing that problem is in hardness “limbo” , shows that are plenty of natural intermediate (conjectured to be incomplete) sets inside NP. It is known that $ P \ne NP$ if and only if there exists an incomplete set in $NP$.

What evidence do we have to supports the belief that current theory of NP-completeness can not prove the existence of incomplete sets in NP? Does the situation change if we use weaker reductions such as logspace many-one or $AC^0$ instead of Karp reduction?