Informationsasymmetri är ett centralt problem i både datavetenskap och ekonomi. I många grundläggande problem vill en oinformerad rektor skaffa sig viss kunskap från en opålitlig expert. Detta modellerar flera verkliga situationer, såsom en chefs relation med sina anställda, eller delegering av beräkningsuppgifter i mekanisk turk. Eftersom experten är opålitlig, behöver huvudmannen en viss garanti för att den kunskap som ges är korrekt. Inom datavetenskapen ges denna garanti vanligtvis via ett bevis som huvudmannen kan verifiera. En oärlig expert kommer därför att bli fångad och straffad (med mycket stor sannolikhet). I många ekonomiska sammanhang ges vanligen garantier för att kunskapen är korrekt via incitament. Det vill säga, ett spel spelas mellan expert och rektor så att experten maximerar hennes nytta genom att vara ärlig. Ett rationellt bevis är ett interaktivt bevis där bevisaren, Merlin, varken är ärlig eller illvillig, utan rationell. Det vill säga, Merlin agerar för att maximera sin egen nytta. Rationella bevis har tidigare studerats när kontrollören, Arthur, är en probabilistisk polynomtidsmaskin [1]. I denna uppsats studerar vi supereffektiva rationella bevis, det vill säga rationella bevis där Arthur kör i logaritmisk tid. Våra nya rationella bevis är mycket praktiska. De är inte bara mycket snabbare än sina klassiska analoger, utan de ger också mycket påtagliga incitament för experten att vara ärlig. Arthur behöver bara en polynom-budget, men han kan straffa Merlin med en stor mängd om han avviker från sanningen. Vi ger följande karakteriseringar av vilka problem medger supereffektiva rationella bevis. (1) Enhetlig T C 0 sammanfaller med den uppsättning språk L som medger ett rationellt bevis med hjälp av O(log n) tid, O(log n) kommunikation, ett konstant antal rundor och en polynom storlek budget. (2) P N P sammanfaller med den uppsättning språk som har ett rationellt bevis med hjälp av O(log n) tid, poly(n) kommunikation, en runda och en polynom storlek budget. Dessutom visar vi att när Arthur är begränsad till att ha en polynom-storlek budget, den uppsättning språk som medger rationella bevis med polynom tidverifiering, polynom kommunikation och en runda är P A
I ett uppföljningsarbete REF, författarna designar super-effektiva rationella bevis som har sublinjär verifiering och beräkning tvingarexitet.
Super-efficient rational proofs
{'venue': "EC '13", 'journal': None, 'mag_field_of_study': ['Computer Science']}