Abstrakt. I detta dokument presenteras en ny uppfattning om ett bevis som bygger på beräkningskomplexitet och undersöker dess konsekvenser för beräkning i stort. Computationally sunda bevis ger, i en ny och meningsfull ram, svar på gamla och nya frågor i komplexitetsteori. I synnerhet, med tanke på ett slumpmässigt orakel eller en ny komplexitet antagande, de gör det möjligt för oss att 1. bevisa att verifiering är lättare än att besluta för alla teorem; 2. ge ett ganska effektivt sätt att bevisa medlemskap i beräkning svårt språk (såsom Co-N P-fullständiga); och 3. visa att varje beräkning har ett kort certifikat som går i god för sin korrekthet. Slutligen, om det finns en speciell typ av beräkningsunderlag, visar vi att Blums uppfattning om programkontroll kan breddas på ett meningsfullt sätt för att bevisa att N P-kompletterade språk är kontrollerbara. Nyckelord. Interactive proofs, probabilistically kontrollable proofs, slumpmässiga oracles, Merkle träd PII. S0097539795284959 1. Inledning. KS-bevis. Bevis är grundläggande för våra liv, och när det gäller allt som är grundläggande bör vi förvänta oss att besvara frågan om vad ett bevis är alltid kommer att vara en pågående process. Vi vill faktiskt lägga fram den nya idén om ett beräkningsunderlag (CS-bevis) som uppnår nya och viktiga mål, som inte har uppnåtts eller ens tagits upp i tidigare föreställningar. Informellt, ett CS-bevis för ett uttalande S består av en kort sträng, σ, som (1) är så lätt att hitta som möjligt, (2) är mycket lätt att verifiera, och (3) erbjuder en stark beräkningsgaranti om den verkliga S. Genom att "så lätt att hitta som möjligt" menar vi att ett CS-bevis för ett sant uttalande (dvs. för detta papper, härleds i en given axiomatisk teori) kan beräknas på en tid nära den som behövs för Turing-accept S. Med "mycket lätt att verifiera" menar vi att den tid som krävs för att inspektera ett CS-bevis för ett uttalande S är betydligt mindre än den tid som krävs för Turing-accept S. Slutligen, genom att säga att den garanti som erbjuds av ett CS-bevis är "beräkning" menar vi att falska uttalanden antingen inte har några CS-bevis, eller sådana "bevis" är praktiskt taget omöjliga att hitta. Genomförande av CS-bevis. Värdet av ett nytt begrepp beror naturligtvis på om det kan exemplifieras tillräckligt. Vi tillhandahåller två huvudimplementeringar av vårt koncept. Den första är baserad på en slumpmässig orakel och ger bevis på ett CS-bevissystem utan något obevisat antagande. Den andra bygger på en ny komplexitet antagande: i huvudsak, att det är möjligt att ersätta slumpmässiga orakel av den första konstruktionen med en kryptografisk funktion och få, i tillämpliga delar, liknande resultat. Tillämpningar av CS-bevis. I antingen genomförande, CS-bevis ger, i en ny och meningsfull ram, mycket naturliga svar på några av våra äldsta frågor i komplexitetsteori. I synnerhet innebär de inte bara att den tid som krävs för att kontrollera är betydligt mindre än den tid som krävs för att godta, utan, vilket är ännu viktigare,
I synnerhet ger Micalis arbete REF en lösning för icke-interaktiv kontrollerbar beräkning i den slumpmässiga orakelmodellen.
COMPUTATIONALLY SOUND PROOFS
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Computer Science']}