Gibt es für jede berechenbare Funktion eine äquivalente Rechenschaltung?
Ich habe versucht, mich mit der obigen Aussage zu beschäftigen, aber kein Gegenbeispiel gefunden, obwohl ich glaube, dass die Aussage falsch ist.
Was mich neugierig gemacht hat, ist, dass ich einige Theoreme gelesen habe, die besagen, dass ein Protokoll (Kryptographieprotokolltheorie) jede berechenbare Funktion berechnen kann, dann aber erfordert, dass die Funktion als arithmetische Schaltung angegeben wird.
Antworten:
Arithmetische Schaltungen berechnen in ihrer Eingabe ein Polynom. Eine arithmetische Schaltung über ein Feld mit Variablen und dem Gesamtgrad kann die Funktionen der folgenden Form berechnen :F. n d f::F.n→ F.
Dabei sind die Koeffizienten des multivariaten Polynoms.αich1, . . . ,ichn∈ F.
Es gibt viele berechenbaren Funktionen, die nicht als ein Polynom ausgedrückt werden, zum Beispiel nehmen , das ist bei und Null überall sonst. Da mit einer unendlichen Anzahl von Nullen nicht konstant ist, kann es nicht als univariates Polynom geschrieben werden.f: Q → Q. 1 x = 0 f
quelle
Jede berechenbare boolesche Funktion mit einer Eingabe fester Länge kann durch eine arithmetische Schaltung berechnet werden. Betrachten Sie eine boolesche Funktionf: { 0 , 1}}n→ { 0 , 1 } . Dann existiert ein multivariates Polynom so dass für alle , wobei die Arithmetik modulo durchgeführt wird zwei (dh über dem Feld ). Jetzt kann jedes multivariate Polynom durch eine arithmetische Schaltung berechnet werden, so dass durch eine arithmetische Schaltung berechnet werden kann.p (x1, … ,xn) f(x1, … ,xn) = p (x1, … ,xn) x1, … ,xn F.2= { 0 , 1 } f
In gewissem Sinne sind die Einschränkungen für Eingänge fester Länge unvermeidbar, da jede Schaltung von Natur aus eine feste Anzahl von Eingängen und eine feste Anzahl von Ausgängen aufweist. Wenn Sie sich also auf boolesche Funktionen konzentrieren, ist die Aussage, die Sie in der Kryptoliteratur gesehen haben, gerechtfertigt: Jede boolesche Funktion, die von einer Schaltung berechnet werden kann, kann von einer arithmetischen Schaltung berechnet werden. Und jede berechenbare boolesche Funktion kann durch arithmetische Schaltungen berechnet werden, wobei wir unter "berechnet" verstehen, dass es eine Familie von arithmetischen Schaltungen gibt, eine pro Eingangslänge (das ungleichmäßige Modell; dies ist unvermeidlich, wenn Sie mit berechnen möchten Schaltungen, da jede Schaltung nur eine feste Eingangslänge haben kann).
quelle