<p>If I understand correctly your questions are answered in </p>

<p><a href="http://link.springer.com/article/10.1007%2Fs00037-001-8191-1" rel="nofollow">Agrawal-Allender-Impagliazzo-Pitassi-Rudich-2001: Reducing the Complexity of Reductions</a></p>

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

CC BY-SA 3.0
2015-01-24T18:47:19.720Z
I think this is for the first question. How about the second?
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-01-24T19:31:09.013Z
Item 2 answers the second question as well. The stop gap theorem implies that there exists a set that is not complete under NC^0 reductions as well.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2015-01-24T18:19:27.230Z
2015-01-25T01:39:53.383Z
2015-01-25T01:39:53.383Z
Mateus de Oliveira Oliveira
<p>Ladner theorem can be stated as:</p>

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

<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$.</p>

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

<p>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.</p>

<blockquote>
  <p>Does there exist an incomplete $NP$ set under $NC^0$ reductions?</p>
</blockquote>

<cc.complexity-theory><reductions>
The relationship between completeness and strength of reductions
Mohammad Al-Turkistany
# The relationship between completeness and strength of reductions

(Asked by: username_0 on 2015-01-24)

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?

**Tags:** cc.complexity-theory, reductions

---

## 1 answers

### Answer by username_1 on 2015-01-24. Score: 9 | Accepted answer

If I understand correctly your questions are answered in

[Agrawal-Allender-Impagliazzo-Pitassi-Rudich-2001: Reducing the Complexity of Reductions](http://link.springer.com/article/10.1007%2Fs00037-001-8191-1)

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.

> **Comments:**
> **username_0**: I think this is for the first question. How about the second?  
> **username_1**: Item 2 answers the second question as well. The stop gap theorem implies that there exists a set that is not complete under NC^0 reductions as well.  

---

