Une preuve interactive pour HORN-SAT?

Existe-t-il un moyen pour un prouveur de convaincre un vérificateur qu'une expression HORN-SAT est satisfaisable?

Bien sûr, cela peut sembler idiot, car il existe des algorithmes de temps linéaires pour HORN-SAT. D'un autre côté, HORN-SAT est P-complet, ce qui signifie qu'il n'a pas d'algorithmes d'espace de log à moins que P = L. Par conséquent, limitez les capacités de calcul du vérificateur à L. Maintenant, le vérificateur est très faible, donc le problème n'est plus idiot.

Une autre tournure à ce sujet est de savoir s'il peut s'agir d'une preuve de connaissance zéro.

cc.complexity-theory interactive-proofs zero-knowledge Shaun Harker
la source

Dans le cas de la connaissance non nulle, je pense que la vérification naïve utilisant une affectation de vérité satisfaisante comme certificat ne nécessite que de l'espace de journal, à condition que l'entrée et le certificat soient écrits sur des bandes en lecture seule qui ne comptent pas comme de l'espace.

Tsuyoshi Ito

@Tsuyoshi: Je ne vois pas comment faire une vérification naïve uniquement dans l'espace de journalisation. Si nous le pouvions, cela ne montrerait-il pas que HORN-SAT est en NL, et donc par P-complétude donner P = NL?

Shaun Harker

Non. J'ai supposé que le certificat était sur une bande en lecture seule, ce qui est différent de la vérification effectuée par NL.

Tsuyoshi Ito

@Tsuyoshi: Ah, vous pouvez donc lire le certificat plusieurs fois, alors qu'une définition basée sur un certificat de NL aurait un certificat qui ne peut être lu qu'une seule fois.

Shaun Harker

Réponses:

Cette enquête http://www.cs.ubc.ca/~condon/papers/ips-survey.pdf d'Anne Condon contient de nombreux faits sur les systèmes de preuve interactifs délimités par l'espace.

Il existe plusieurs modèles, et les principales différences sont de savoir si vous autorisez les pièces privées pour le vérificateur (IP) ou les pièces publiques uniquement (AM), et si vous limitez également le temps de vérification au polynôme (non impliqué par l'espace lié uniquement).

Sans restriction de temps, la réponse est oui: IP (espace de journal) contient EXP et AM (espace de journal) = P.

Notez que l'IP (espace de journal) est probablement plus grand que l'IP standard. Par contre IP (log-space, poly-time) = IP = PSPACE.

AM (log-space, poly-time) = P due à 'Delegating Computation: Interactive Proofs for Muggles' de Goldwasser et al., STOC 2008.

De plus, l'article `` Zero knowledge with log-space verifiers '' de Kilian (FOCS 88) montre comment obtenir un système de preuve de connaissance zéro dans l'espace logarithmique pour tout en IP (avec des pièces privées évidemment).

Hartmut Klauck
la source

J'ai également trouvé un article intitulé Délégation du calcul: preuves interactives pour les moldus . Le théorème 3 de ce travail montre-t-il que AM (log-space, poly-time) = P?

Shaun Harker

Oui, ils le montrent bien!

Hartmut Klauck