Ramen för algoritmisk kunskap förutsätter att agenter använder deterministiska kunskapsalgoritmer för att beräkna de fakta de uttryckligen känner till. Vi utökar ramverket för att möjliggöra randomiserade kunskapsalgoritmer. Vi karakteriserar sedan den information som ges av en randomiserad kunskapsalgoritm när dess svar har viss sannolikhet att vara felaktiga. Vi formaliserar denna information i termer av bevis; en randomiserad kunskapsalgoritm som återvänder "Ja" till en fråga om ett faktum ~o ger bevis för att qo är sant. Slutligen diskuterar vi i vilken utsträckning dessa bevis kan användas som underlag för beslut. Algoritmisk kunskap är ett mycket allmänt tillvägagångssätt. Berman, Garay och Perry [1989] använder till exempel implicit en viss form av algoritmisk kunskap i sin analys av bysantinsk överenskommelse. Ungefär som de tillåter agenter att utföra begränsade tester baserat på den information de har; agenter vet bara vad som följer av dessa begränsade tester. Ramanujam [1999] undersöker *en särskild form av algoritmisk kunskap, där kunskapsalgoritmen i huvudsak är ett modellkontrollförfarande för en standardlogik för kunskap. Mer specifikt, Ramanujam anser, i varje tillstånd, plm av modellen som en viss agent ser (till exempel, en agent i ett distribuerat system kan vara medveten endast om sina närmaste grannar, de med vilka han kan kommunicera) och tar som kunskap algoritm modell-kontroll förfarande för epistemisk logik, tillämpas på den undermodell som genereras av de synliga tillstånden. Halpern och Pucella [2002] har tillämpat algoritmisk kunskap på säkerhet för att fånga inkräktare som är resursbegränsade (och därmed, till exempel, inte kan faktor de produkter av stora primer som uppstår i RSA cryptosystem [Rivest, Shamir, och Adelman 1978] ). Alla dessa exempel använder ljudkunskapsalgoritmer: även om algoritmen inte kan ge ett svar under alla omständigheter, när den säger "Ja" på input qo, vet agenten verkligen 79 i den vanliga möjliga-världar känsla. Även om sundhet inte krävs i den grundläggande definitionen, verkar det vara användbart i många tillämpningar. Vårt intresse för denna uppsats är kunskapsalgoritmer som kan använda någon randomisering. Som vi ska se finns det många exempel på naturliga randomiserade kunskapsalgoritmer. Med randomisering, oavsett om kunskapsalgoritmen säger "Ja" kan bero på resultatet av myntkast. Detta innebär en liten svårighet att ens ge semantik till algoritmisk kunskap, eftersom standardsemantiken bara är meningsfull för deterministiska algoritmer. För att ta itu med detta problem gör vi algoritmerna deterministiska genom att förse dem med ett extra argument (intuitivt, resultatet av en sekvens av myntkast) för att "derandomisera" dem. Vi visar att detta tillvägagångssätt ger en naturlig förlängning av det deterministiska fallet. För att motivera användningen av randomiserade kunskapsalgoritmer överväger vi ett säkerhetsexempel från Halpern och Pucclla [2002]. Ramen i det dokumentet låter oss resonera om principer som kommunicerar i närvaro av motståndare, med hjälp av kryptografiska protokoll. Det typiska antagandet som görs vid analys av säkerhetsprotokoll är att motståndare kan avlyssna alla meddelanden som utbyts av huvudmännen, men kan inte nödvändigtvis dekryptera krypterade meddelanden om de inte har lämplig dekrypteringsnyckel. För att fånga exakt motståndares kapacitet använder vi kunskapsalgoritmer. Ungefär, en kunskapsalgoritm för en motståndare kommer att ange vilken information motståndaren kan extrahera från avlyssnade meddelanden. I detta dokument betraktar vi en motståndare som ytterligare försöker gissa de kryptografiska nycklar som används av huvudmännen i protokollet. Vi visar hur man fångar kunskapen hos en sådan motståndare med hjälp av en randomiserad kunskapsalgoritm. Efter att ha definierat ramverket försöker vi karakterisera den information som erhålls genom att få ett "Ja" svar på en fråga för ~o. Om kunskapsalgoritmen är ljud, så garanterar ett ja-svar att 79 är sant. Men, de randomiserade algoritmer av mest intresse för oss ge felaktiga svar med positiv sannolikhet, så är inte ljud. Ändå verkar det säkert att om sannolikheten att algoritmen ger fel svar är låg, ger det mycket användbar information när det står "Ja" till en fråga ~. Denna intuition visas i den randomiserade algoritmlitteraturen, där ett "ja" svar från en mycket tillförlitlig randomiserad algoritm som är, en med låg sannolikhet för att vara fel, anses vara "bra nog". I vilken bemärkelse är detta sant? Ett bidrag till vårt arbete är att ge ett formellt svar på den frågan. Det kan tyckas att ett "Ja" svar på en fråga 79 från en mycket tillförlitlig randomiserad kunskapsalgoritm bör göra sannolikheten att 79 är sant vara hög men, som vi visar, detta är inte nödvändigtvis sant. I stället bör informationen betraktas som bevis för att 79 är sant. Sannolikheten för att 79 är sant beror också delvis på den tidigare sannolikheten för 79. I litteraturen har man i stor utsträckning studerat bevis på induktiv logik [Kyburg 1 983]. Bevis för en viss hypotes kan samlas från olika källor, och det är möjligt att kombinera
Målet för författarna till REF ) är "att förstå vad de bevis som tillhandahålls av en kunskapsalgoritm talar om för oss."som är en helt annan än vår.
Probabilistic algorithmic knowledge
{'venue': "TARK '03", 'journal': None, 'mag_field_of_study': ['Computer Science']}