# The relationship between completeness and strength of reductions

Ladner theorem can be stated as:

$P \ne NP$ if and only if there exists an incomplete set in $NP-P$.

Here an incomplete set is a set that is not complete for $NP$ under many-one polynomial time reductions (Karp reduction). Therefore, existence of any incomplete problem in $NP$ would immediately imply $P \ne NP$.

Is there a many-one reduction weaker than Karp reduction for which we can prove the existence of incomplete sets in $NP$?

An example of weak reductions is $NC^0$ many-one reduction (using circuits of polynomial size, constant depth, and bounded fan-in). In an $NC^0$ reduction, each output bit of the reduction can depend only on a constant number of input bits. Many $NP$-complete problems remain complete under $NC^0$ reductions.

Does there exist an incomplete $NP$ set under $NC^0$ reductions?

1. Gap Theorem - Any set that is NP-complete under $AC^0$ reductions is NP-complete under $NC^0$ reductions.
2. Stop Gap Theorem - There is a set that is NP-complete under $AC^0[\!\!\mod 2]$ reductions, but not under $AC^0$ reductions.