Erkennungsschaltung, die in Funktionalität und Implementierung ähnlich ist

Sei ein Vektor boolescher Variablen. Sei zwei boolesche Schaltungen auf . Sagen Sie, dass ähnlich ist, wenn:$x=(x_1,\dots,x_n)$$C,D$$x$$C$$D$

1. $\Pr[C(x) \ne D(x)]$ ist exponentiell klein, wenn $x$ gleichmäßig zufällig aus \ {0,1 \} ^ n gezeichnet wird $\{0,1\}^n$(mit anderen Worten, sie haben eine nahezu identische Funktionalität); und,

2. $C,D$ unterscheiden sich in der Grafikbearbeitungsentfernung um einen winzigen Betrag (ihre Bearbeitungsentfernung ist viel kleiner als die Größe der Schaltung, z. B. $O(1)$ oder eine kleine Konstante), was bedeutet, dass fast alle Gates und Drähte von $C$ übereinstimmen ein entsprechendes Gate und Draht in $D$ , wobei nur wenige Gates hinzugefügt / gelöscht / geändert wurden.

Mein Problem: Ich bekomme eine Schaltung $C$ und möchte wissen, ob es eine Schaltung $D$ gibt, die C ähnlich, $C$aber nicht identisch mit $C$ (dh wo es x gibt, $x$so dass $C(x)\ne D(x)$ ).

Kann jemand einen Algorithmus vorschlagen, um dieses Problem zu lösen?

Wenn es hilft, können wir die Aufmerksamkeit auf Schaltungen $D$ , die kleiner als die gegebene Schaltung $C$ (dh wir möchten wissen, ob es eine Schaltung $D$ so dass $D$ kleiner als $C$ , $D$ ähnlich zu $C$ ist und x existiert $x$so dass $C(x)\ne D(x)$ ).

Wenn es hilft, können Sie zusätzlich annehmen, dass wir bekanntermaßen gute Testfälle $x^1,\dots,x^m,y^1,\dots,y^m$ so dass $C(x^i)=y^i$ für all $i$ , und wir können die Aufmerksamkeit weiter auf nur Schaltungen $D$ so dass $D(x^i)=y^i$ für alle $i$ .

Dies ergibt sich aus einer praktischen Anwendung. Wenn Sie dieses Problem nicht lösen können, können Sie jede Variante oder jeden interessanten Sonderfall lösen. Sie können beispielsweise einen der Parameter oder Schwellenwerte auf eine für Sie geeignete Weise instanziieren. Sie können davon ausgehen, dass die Schaltkreise nicht zu groß sind (Polynomgröße oder ähnliches). Sie können die Bearbeitungsentfernung für Diagramme durch ein anderes Maß für die nahezu übereinstimmende Implementierung ersetzen. In der Praxis sind SAT-Löser in den in der Praxis auftretenden strukturierten Schaltkreisen häufig überraschend effektiv. Daher ist es wahrscheinlich in Ordnung, einen SAT-Löser als Subroutine / Orakel aufzurufen (zumindest, wenn Sie ihn in einer abgeleiteten SAT-Instanz aufrufen von einem Stromkreis wie ).$C$

Wenn mir keine Algorithmen fehlen, würde mich auch die Existenzfrage interessieren: Wie groß ist für eine "durchschnittliche" Schaltung die Wahrscheinlichkeit, dass existiert , das alle Kriterien erfüllt? (Ich hoffe, diese Wahrscheinlichkeit ist sehr gering, aber ich habe keine Ahnung, ob dies der Fall ist.)$C$$D$

Die praktische Anwendung besteht darin, zu testen, ob eine Schaltung eine böswillige Hintertür / ein verstecktes Osterei enthalten könnte. Die Hypothese, wie so etwas eingefügt werden könnte, lautet wie folgt. Wir beginnen mit einer "goldenen" Schaltung , die die gewünschte Funktionalität berechnet und keine versteckte Hintertür hat. Dann nimmt der Gegner eine kleine Änderung an , um die verborgene Hintertür einzuführen und eine modifizierte Schaltung . Der Zweck der Hintertür besteht darin, die von berechnete Funktion auf irgendeine Weise zu ändern . Wenn nicht zu klein ist, kann die Änderung plausibel durch zufällige Tests erkannt werden, sodass ein Gegner wahrscheinlich versuchen wird,$C$$D$$D$$C$$D$$\Pr[C(x) \ne D(x)]$$\Pr[C(x) \ne D(x)]$sehr klein. Wenn sich an zu vielen Stellen von unterscheidet , kann dies durch zufällige Inspektion der Schaltung bemerkt werden, sodass ein Gegner wahrscheinlich versuchen wird, die Anzahl der Änderungen zu minimieren. (Und es kann eine Testsuite von Paaren geben, die Instanzen der gewünschten Funktionalität darstellen, so dass wir wissen, dass unabhängig von der "goldenen" Schaltung erfüllt ist für alle .) Letztendlich erhalten wir die Schaltung (aber nicht die "goldene" Schaltung ), und wir wollen wissen, ob eine modifizierte Version von einigen$C$$D$$x^i,y^i$$D$$D(x^i)=y^i$$i$$C$$D$$C$$D$, wo die Änderung vorgenommen wurde, um eine versteckte Hintertür dieser Art einzuführen.

Dies ist nur ein ausführlicher Kommentar, der mir unmittelbar nach dem Lesen der Frage in den Sinn kam:

• Angenommen, Sie haben eine 3SAT-Formel mit Variablen und lassen die entsprechende Schaltung sein;$\phi$$n$$x_1,...,x_n$$C$

• Bauen Sie eine neue Schaltung , indem Sie Variablen und genügend Gatter hinzufügen, um UND die neuen Variablen mit der Ausgabe des ursprünglichen ( );$C'$$m = n^k$$y_1, y_2, ...,y_{n^k}$$m$$C$$C' = \phi \land y_1 \land ... \land y_m$

• Erstellen Sie eine neue Schaltung aus , die ihren Ausgang einfach mit einem UND- und NICHT-Gatter auf 0 zwingt ( ).$D'$$C'$$D' = C' \land \neg C'$

Wenn nicht erfüllbar ist, sind und äquivalent, andernfalls unterscheiden sie sich, wenn die Formel UND alle erfüllt , aber Sie können groß genug wählen , um die Wahrscheinlichkeit, dass sehr klein ist , zu .$\phi$$D'$$C'$$x_i$$y_i = 1$$m$$\bigwedge y_i = 1$

Wenn Sie also einen effizienten Algorithmus für Ihr Problem haben, können Sie die 3SAT-Instanz effizient lösen.