prikaz prve stranice dokumenta Interaktivni dokazi
  Preuzmi
PDF 252.54 KB
diplomski rad
Interaktivni dokazi
Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2022. urn:nbn:hr:217:018568
Žufić, Ivan
Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
Matematički odsjek

Institucijski repozitorij: Repozitorij Prirodoslovno-matematičkog fakulteta

Citirajte ovaj rad

Žufić, I. (2022). Interaktivni dokazi (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:217:018568

Žufić, Ivan. "Interaktivni dokazi." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2022. https://urn.nsk.hr/urn:nbn:hr:217:018568

Žufić, Ivan. "Interaktivni dokazi." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2022. https://urn.nsk.hr/urn:nbn:hr:217:018568

Žufić, I. (2022). 'Interaktivni dokazi', Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, citirano: 29.04.2024., https://urn.nsk.hr/urn:nbn:hr:217:018568

Žufić I. Interaktivni dokazi [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet; 2022 [pristupljeno 29.04.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:018568

I. Žufić, "Interaktivni dokazi", Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, Zagreb, 2022. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:018568

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:217:018568
Podaci o radu
NaslovInteraktivni dokazi
Naslov (engleski)Interactive proof
AutorIvan Žufić
MentorMarko Horvat (mentor)
Član povjerenstvaMarko Horvat (predsjednik povjerenstva)
Član povjerenstvaZvonko Iljazović (član povjerenstva)
Član povjerenstvaNenad Antonić (član povjerenstva)
Član povjerenstvaHrvoje Planinić (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
(Matematički odsjek)
Zagreb
Datum i država obrane2022-05-05, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Sažetak
U ovom radu opisujemo IP, klasu problema rješivih u polinomnom vremenu koristeći sustave interaktivnih dokaza. Sustavi interaktivnih dokaza koriste interakciju dva stroja, dokazivača i verifikatora, za odlučivanje pripadnosti neke riječi nekom formalnom jeziku. Dokazivač je stroj s neograničenim vremenskim i memorijskim računskim mogućnostima, dok je verifikator Turingov stroj kojem dodatno omogućavamo generiranje slučajnih bitova. Dokazivač pokušava uvjeriti verifikatora u pripadnost riječi jeziku, dok verifikator pokušava provjeriti istinitost te tvrdnje. Za razliku od mnogih drugih klasa, dopuštamo verifikatoru malu mogućnost pogreške. Omogućavanje generiranja slučajnih bitova i dopuštanje pogrešaka možda ne izgleda značajno, ali ispostavlja se da je klasa IP ekvivalentna klasi PSPACE, što i dokazujemo u ovom radu. Razmatramo i varijantu interaktivnih dokaza u kojoj su verifikatorovi slučajno generirani bitovi javno dostupni. U posljednjem poglavlju navodimo neke primjene interaktivnih dokaza u kriptografiji.
Sažetak (engleski)
In this paper, we present IP, the class of problems solvable in polynomial time using interactive proof systems. Interactive proof systems use the interaction of two machines, a prover and a verifier, to check if some word is in some formal language. The prover is a machine with unlimited computing power, while the verifier is a Turing machine which can generate random bits. The prover’s task is to convince the verifier that the word is indeed in the language, while the verifier’s task is to check the truthfulness of that claim. We allow a small chance of the verifier failing in its task. Enabling random bit generation and allowing mistakes might look insignificant, but it turns out that the class IP is equivalent to the class PSPACE, which we prove in this paper. We also consider a variant of interactive proofs in which the verifier’s randomly generated bits are publicly available to the prover. In the final chapter, we mention some applications of interactive proofs in cryptography.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:217:018568
Studijski programNaziv: Računarstvo i matematika
Vrsta studija: sveučilišni
Stupanj studija: diplomski
Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2022-06-09 10:26:17