Vi studerar interaktiva bevis med underlinjära tidskontrollanter. Dessa bevissystem kan användas för att säkerställa ungefärlig korrekthet för resultaten av beräkningar som delegerats till en opålitlig server. Efter litteraturen om fastighetsprövning söker vi bevissystem där kontrollören med stor sannolikhet accepterar varje inmatning i språket och avvisar varje inmatning som är långt ifrån språket. Kontrollörens frågekomplexitet (och beräkningskomplexitet), liksom kommunikationen, bör alla vara sublinjära. Vi kallar ett sådant bevissystem ett Interactive Proof of Proximity (IPP). • På den positiva sidan, vårt främsta resultat är att alla språk i N C har Interactive Proofs of Proximity med ungefär ε n fråga och kommunikation och komplexitet, och polylog(n) kommunikationsrundor. Detta uppnås genom att identifiera ett naturligt språk, medlemskap i en affin subrymd (för en strukturerad klass av subrymder), som är komplett för att bygga interaktiva bevis på närhet, och tillhandahålla effektiva protokoll för det. Genom att bygga en IPP för detta fullständiga språk, visar vi en kompromiss mellan frågan och kommunikation komplexitet och antalet rundor. Till exempel ger vi ett 2-runda protokoll med ungefär n 3/4 frågor och kommunikation. • På den negativa sidan, Vi visar att det finns naturliga språk i N C 1, där summan av frågor och kommunikation i varje konstant-runda interaktiva bevis på närhet måste polynomiskt relaterade till n. I synnerhet, för alla 2-runda protokoll, summan av frågor och kommunikation måste vara minst. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. • Slutligen bygger vi mycket bättre IPPs för specifika funktioner, såsom tvåpartiitet på slumpmässiga eller välmixande grafer, och majoriteten funktion. Förfrågan komplexiteten i dessa protokoll är bevisligen bättre (av exponentiella eller polynomiska faktorer) än vad som är möjligt i standard egendom testning modell, dvs.. utan bevis.
På den negativa sidan visar REF att det finns ett språk i N C 1 för vilket summan av frågor och kommunikation i varje konstant runda interaktiva bevis på närhet måste polynomiskt relaterade till n.
Interactive proofs of proximity: delegating computation in sublinear time