Vollständigkeit unter Karp-Injektionsreduktionen

Die Karp-Reduktion ist eine polynomielle Zeitberechnungsreduktion um ein Vielfaches zwischen zwei Rechenproblemen. Viele Karp-Reduktionen sind eigentlich Ein-Eins-Funktionen. Dies wirft die Frage auf, ob jede Karp-Reduktion injektiv ist (Eins-Eins-Funktion).

Gibt es ein natürliches -komplettes Problem, von dem bekannt ist, dass es nur bei einer Karp-Reduktion um ein Vielfaches vollständig ist, und von dem nicht bekannt ist, dass es bei einer Karp-Reduktion durch Injektion vollständig ist? Was gewinnen wir (und verlieren) , wenn wir definieren N P -completeness mit injektiv Karp Reduktion?$NP$$NP$

Ein offensichtlicher Vorteil ist, dass spärliche Sets unter Karp-Reduktionen nicht vollständig sein können.

Hier ist eine Antwort auf einen speziellen Fall, wenn wir uns auf den Fall beschränken , wenn die Karp Reduktion kann auch erfolgen Länge steigernde , zusammen mit so dass es injektiv. (Längenerhöhung bedeutet, dass , wobei f die Funktion ist, die die Reduktion darstellt.)$|f(x)|>|x|$$f$

Ansprüche: Wenn jede Karp Reduktion in kann in eine transformiert werden , die injektiv und längen zunimmt, dann P ≠ N P hält.$NP$$P\neq NP$

Beweis. Nehmen wir an, dass jede Karp-Reduktion von in eine injizierende und längenerhöhende umgewandelt werden kann. Dann gibt es zwei Möglichkeiten:$NP$

1. Alle diese Verringerungen sind nicht nur in der Polynomzeit berechenbar, sondern die Umkehrung jeder Funktion, die nach dem Injizieren der Funktion existiert, ist auch in der Polynomzeit berechenbar. Es ist bekannt, dass wenn zwei Sprachen durch Reduktionen, die polyzeitberechenbar, polyzeitinvertierbar und längenerhöhend sind, beide zueinander reduzierbar sind, sie polyzeitisomorph sind (siehe Satz 7.4 im Buch "Theory of Computational Complexity" von Ding-Zhu Du und Ker-I Ko). Dies würde bedeuten, dass alle vollständigen Sprachen p -isomorph sind, das heißt, die Isomorphismus-Vermutung ist gültig, was bekanntlich P ≠ N P impliziert .$NP$$p$$P\neq NP$

2. Es gibt mindestens eine dieser Funktionen, für die die Inverse in der Polynomzeit nicht berechenbar ist. Diese Funktion würde ein Beispiel für eine Einwegfunktion im ungünstigsten Fall liefern. Es ist jedoch bekannt, dass die Existenz von Einwegfunktionen im ungünstigsten Fall auch impliziert . (Siehe Satz 2.5 im Buch "The Complexity Theory Companion" von Hemaspaandra und Ogihara.)$P\neq NP$

Daher impliziert die Annahme, dass jede Karp-Reduktion injektiv und längenerhöhend gemacht werden kann, , so dass es sehr schwer zu beweisen ist. Andererseits könnte es einfacher sein, dies zu widerlegen, da dies keine so dramatische Konsequenz zu haben scheint. Es ist auch unklar, was passiert, wenn wir die Annahme fallen lassen, dass die Länge zunimmt.$P\neq NP$

$\mathsf{NP}$$\mathsf{NP}$

Tatsächlich sind sogar die potentiellen "unnatürlichen" Gegenbeispiele zur Isomorphismus-Vermutung - die k-kreativen Mengen von Joseph und Youngs Theorem 2.2 - unter Eins-Eins-Reduktion durch Konstruktion vollständig.

[Wiederholt aus meinem Kommentar hier :] Da es sich bei den meisten von uns erstellten Reduktionen um Eins-Eins-Reduktionen handelt, warum untersuchen wir diese nicht, wenn sie formal stärker sind und wir sie trotzdem die meiste Zeit erhalten? Ich denke, weil es einfacher ist, sich nicht die Mühe zu machen, die Injektivität zu beweisen, obwohl wir es normalerweise haben. In diesem Sinne sind viele Reduzierungen vielleicht eine Art der "Goldilocks-Reduzierungen": genau die richtige Kraft, genau die richtige Einfachheit des Beweises.

Tatsächlich sind injizierende Reduktionen in der Kryptographie nützlich. Angenommen, Sie haben ein ZK-Beweissystem für eine NP-Relation R über der Sprache L. Wenn Sie einen ZK-Beweis für eine andere NP-Relation R 'über einer Sprache L' erstellen möchten, müssen Sie zwei Funktionen f und g mit den folgenden Eigenschaften finden : 1. x gehört zu L 'wenn f (x) zu L gehört, 2. wenn (x, w) zu R' gehört, dann gehört (f (x), g (x, w)) zu R. 3. Außerdem , f und g müssen effizient berechenbar sein.

Die obigen Eigenschaften implizieren, dass, wenn das Beweissystem für R vollständig und solide ist, das Beweissystem für R '(das auf offensichtliche Weise unter Verwendung der obigen Funktionen definiert wird, um die Fälle einer Beziehung zu dem anderen zu reduzieren) auch vollständig und solide ist.

Was ist mit dem Nachweis, dass das neue System auch ZK oder zeugenununterscheidbar (WI) ist? Wenn f invertierbar ist, können Sie nachweisen, dass das so erhaltene Beweissystem ZK ist. Andernfalls müssen Sie zum Nachweis davon ausgehen, dass das Beweissystem für R der Hilfseingang ZK (und nicht nur ZK) ist. Wenn für WI f invertierbar ist, können Sie nachweisen, dass das Beweissystem für R 'WI ist. Ohne die Tatsache, dass f invertierbar ist, bin ich mir nicht sicher, ob Sie das beweisen können