Titre original :
On Doubly-Efficient Interactive Proof Systems
Contenu du livre :
Un système de preuve interactif est dit doublement efficace si la stratégie prescrite du prouveur peut être mise en œuvre en temps polynomial et si la stratégie du vérificateur peut être mise en œuvre en temps quasi-linéaire. De tels systèmes de preuve mettent les avantages des systèmes de preuve interactifs à la disposition des agents de la vie réelle qui sont limités à l'informatique en temps polynomial.
On Doubly-Efficient Interactive Proof Systems passe en revue certains des résultats connus concernant les systèmes de preuve interactifs doublement efficaces. Il commence par présenter deux constructions simples pour t-no-CLIQUE, où la première construction offre l'avantage d'être généralisée à n'importe quel ensemble « localement caractérisable », et la seconde construction offre l'avantage de préserver la saveur combinatoire du problème. Il se tourne ensuite vers deux constructions plus générales de systèmes de preuve interactifs doublement efficaces : le système de preuve pour les ensembles ayant des circuits (uniformes) à profondeur limitée et le système de preuve pour les ensembles qui sont reconnus en temps polynomial et dans un petit espace.
La présentation de la construction GKR est complète et diffère quelque peu de la présentation originale. Un bref aperçu est fourni pour la construction RRR.
Autres informations sur le livre :
| ISBN : | 9781680834246 |
| Auteur : | |
| Éditeur : | |
| Langue : | anglais |
| Reliure : | Broché |
Achat:
Actuellement disponible, en stock.
