Nulinių žinių įrodymas paaiškintas 2 dalyje: Neinteraktyvūs nulio žinių įrodymai

[ware_item id=33][/ware_item]

Neinteraktyvių žinių be įrodymų pavyzdys: „Sudoku“ ir žaidimo kortos


Mūsų „žinių be įrodymo“ serijos 1 dalyje mes paaiškinome, kaip nulinių žinių įrodymas gali veikti, kai tikrintojas ir patarlė sąveikauja vienas su kitu..

Interaktyvus žinių be įrodymų pranašumas yra tas, kad tik tikrintojas gali būti visiškai įsitikinęs, kad patarlė turi žinių. Bet tai taip pat gali būti trūkumas.

Jei pašaliniai asmenys ir stebėtojai negali patvirtinti teiginio, tada patarėjas turi bendrauti su kiekvienu tikrintoju nepriklausomai - tam reikia laiko ir reikia daug išteklių..

Šioje 2 dalyje apžvelgsime neinteraktyvius nulio žinių įrodymus.

Neinteraktyvūs nulio žinių įrodymai

Neinteraktyvių nulinių žinių įrodymų priežastis yra leisti daugybei stebėtojų efektyviai patikrinti įrodymus.

Mums ne visada reikia, kad žinių, neturinčių žinių, įrodymas nebūtų interaktyvus. Pakankamai dažnai galima rasti patikimą vertintoją, kuris garantuoja už įrodymų vientisumą.

Neinteraktyvių žinių be įrodymų pavyzdys: „Sudoku“ ir žaidimo kortos

„Sudoku“ yra įvairaus sunkumo, tačiau gana paprastų žaidimų žaidimas. Kiekvienoje iš 9 eilučių, 9 stulpelių ir 9 sektorių (pažymėtos storu juoda linija) turi būti kiekvienas skaičius nuo 1 iki 9 tiksliai vieną kartą..

Įsivaizduokite, kad sudoku dėlionės sprendimą yra ypač sunku gauti ir net superkompiuteris skaičiuoja keletą dienų..

Bet kažkas (patarlė) teigia turįs galvosūkio sprendimą ir nori parduoti jį už kainą. Kaip jie gali įrodyti, kad turi sprendimą - neatskleidžiant jo -, todėl tikrintojas yra pasirengęs sumokėti?

Įrodymai:

Proveriui reikia 27 žaidimo kortų (bet kokio kostiumo), kurių numeris 1-9–243.

Dabar patarlė kiekvienoje dėžutėje įdeda tris korteles su numeriu, atitinkančiu teisingą „Sudoku“ sprendimą. E. G., jei teisingas dėžutės atsakymas yra 7, patarlė joje įdės 3 žaidimo kortas, kurių vertė 7.

Ant „Sudoku“ stalo bus matomi kai kurie atsakymai. Ant šių, atsakytų dėžučių, dedamos žaidimo kortelės susidurti. Ant tuščių „Sudoku“ dėžučių dedamos kortelės veidu žemyn.

Norėdami įrodyti, kad visos kortelės yra atsuktos tinkamoje padėtyje (neatskleidžiant sprendimo), patarlė privalo:

  • Paimkite viršutinę kortelę iš kiekvieno eilė ir padaryk 9 polius
  • Paimkite viršutinę kortelę iš kiekvieno stulpelis ir padaryk 9 polius
  • Paimkite likusias korteles iš visų sektorius ir padaryk 9 polius

Paraiškos dėl nulio žinių įrodymo

Po to kiekviena krūva suplakama ir pasukama.

Kiekvienas skaičius nuo 1 iki 9 turi būti rodomas kiekvienoje „Sudoku“ eilutėje, stulpelyje ir sektoriuje. Taigi jei kiekvienoje patarlės kortų krūvoje (iš eilutės, stulpelio ir sektoriaus stulpų) yra kiekviena žaidimo kortelė, kurios vertė 1-9, mes žinome, kad jos turi būti sprendimas.

Paraiškos dėl nulio žinių įrodymo

Reikia pripažinti, kad palyginti jaunas žinių be įrodymų laukas dar nerado sutikimo, kurio jis gali nusipelnyti. Tačiau jie gali pasirodyti labai vertingi.

Daugelis matematinių problemų yra panašios į „Sudoku“ dėlionę (pavyzdžiui, grafiko dažymo problema). Jei mes galime naudoti aukščiau pateiktą principą ir sėkmingai jį pritaikyti įvairioms problemoms, galbūt galėsime efektyviau naudoti ir prekiauti skaičiavimo ištekliais ir matematinėmis problemomis. O galbūt greičiau išspręskite matematinius keblumus.

Kudos į Roneną Gradwohl, Moni Naor, Benny Pinkas ir Guy Rothblum

Nulinių žinių įrodymas paaiškintas 2 dalyje: Neinteraktyvūs nulio žinių įrodymai
admin Author
Sorry! The Author has not filled his profile.