Interactive proofs modellerar en värld där en kontrollör delegerar beräkningar till en opålitlig provare, kontrollera bevisarens påståenden innan han accepterar dem. Dessa bevis har ansökningar om delegering av beräkning, probabilistically kontrollerbara bevis, crowdsourcing, med mera. I vissa av dessa ansökningar kan kontrollören betala provtagaren på grundval av kvaliteten på sitt arbete. Rationella bevis, som introducerades av Azar och Micali (2012), är en interaktiv bevismodell där bevisaren är rationell snarare än opålitlig-han kan ljuga, men bara för att öka sin betalning. Detta gör det möjligt för kontrollanten att utnyttja bevisbördans girighet för att få bättre protokoll: medan rationella bevis inte är mer kraftfulla än interaktiva bevis, protokollen är enklare och effektivare. Azar och Micali poserade som ett öppet problem om flera visare är mer kraftfulla än en för rationella bevis. Vi tillhandahåller en modell som utökar rationella bevis för att tillåta flera visare. I denna modell kan en kontrollör dubbelkontrollera de svar som mottagits genom att fråga flera provare. Kontrollören kan betala provtagarna beroende på kvaliteten på deras arbete och ge dem incitament att tillhandahålla korrekt information. Vi analyserar rationella bevis med flera bevis ur ett komplext-teoretiskt perspektiv. Vi karakteriserar denna modell fullt ut genom att ge snäva övre och nedre gränser på dess kraft. På vägen löser vi Azars och Micalis öppna problem på ett jakande sätt, vilket visar att flera rationella provare är strängt starkare än en (enligt vanliga komplexa-teoretiska antaganden). Vi visar vidare att den fulla kraften av rationella bevis med flera visare kan uppnås med endast två visare och fem rundor av interaktion. Slutligen överväger vi mer krävande modeller där kontrollören vill att bevisens betalning ska minska signifi- * Vi tackar flera anonyma granskare för deras värdefulla feedback, och Sanjoy Das, Andrew Drucker, Silvio Micali och Rafael Pass för deras kommentarer.
Chen, McCauley och Singh Ref studerade rationella bevis som tillåter flera testare, och visade att flera rationella testare är strikt mer kraftfulla än en.
Rational Proofs with Multiple Provers
{'venue': "ITCS '16", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}