Puncte:0

Demonstrarea ieșirii unei funcții generice

drapel ma

Există vreo construcție generică pentru a demonstra corectitudinea rezultatelor unei funcții? Cu alte cuvinte, există o modalitate generală de a prezenta un martor pentru declarație $y = f(x)$?

Mai formal, hai $f: X \rightarrow Y$ să fie o funcție generică. Dat $f$, există vreo modalitate generală de a construi o funcție generatoare de martori $p: X \rightarrow W$ și o propunere $V(x, y, w)$ astfel încât, pentru toți $x$, numai $V(x, f(x), p(x))$ este adevărat și se verifică $V(x, y, w)$ este mai rapid decât calcularea $f(x)$?

Maarten Bodewes avatar
drapel in
Funcțiile unidirecționale nu infirmă acest lucru?
poncho avatar
drapel my
O funcție care poate fi un contraexemplu este funcția $f(x)=0$ (pentru orice $x$); da, este ușor să construiți o propunere pentru acest $f$; Nu știu dacă poți construi unul care să ruleze **mai rapid** decât să calculezi $f$...
drapel ma
@poncho, cred că este o idee destul de corectă.
Wilson avatar
drapel se
Pentru a clarifica, dacă citesc corect. Vă întrebați dacă există o demonstrație succintă și un algoritm de verificare eficient (în timp mai puțin decât evaluarea funcției) pentru a verifica dacă pentru un f, x și y public, y=f(x)?
drapel ma
@Wilson exact! Știu că există pentru unele funcții (de exemplu, funcțiile unidirecționale își pot folosi ieșirea ca martori), așa că mă întreb dacă există un mecanism mai general!
Wilson avatar
drapel se
Luați în considerare o funcție generică f reprezentată de un ansamblu de circuite aritmetice, această problemă nu este rezolvată prin preprocesarea SNARK-urilor? Complexitatea timpului verificatorului este polilogaritmică în complexitatea circuitului. Există, de asemenea, o linie de literatură numită calcul verificabil, care poate și ceea ce cauți.
Wilson avatar
drapel se
Să luăm contraexemplul lui poncho în context. $f(x)=0$ este o funcție calculabilă în timp constant. Astfel, factorii constanți din algoritmul de verificare vor depăși complexitatea logaritmică, dar pentru funcțiile non-triviale, această metodă va depăși evaluarea funcției.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.