3
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

If I understand correctly your questions are answered in

Agrawal-Allender-Impagliazzo-Pitassi-Rudich-2001: Reducing the Complexity of 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.
Improve this answer
$\endgroup$
2
  • $\begingroup$ I think this is for the first question. How about the second? $\endgroup$
    – Mohammad Al-Turkistany
    Jan 24, 2015 at 18:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mateus de Oliveira Oliveira
    Jan 24, 2015 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.