Nous savons que si vous avez une machine PSPACE, elle est suffisamment puissante pour donner une preuve interactive de la hiérarchie polynomiale à n’importe quel niveau. (Et si je me souviens bien, tout ce que vous avez besoin est #P.) Mais si vous voulez donner une preuve interactive de l'...
J'étais (et je suis toujours) vraiment intéressé par la réponse à cette question, car il s'agit d'une variation intéressante sur la complexité des jeux qui n'a pas été résolue, alors j'ai offert une prime. Je pensais que la question d'origine était très probablement trop difficile, alors j'ai posté...
Récemment, Watrous et al ont prouvé que QIP (3) = PSPACE un résultat remarquable. Ce fut pour moi un résultat surprenant pour le moins et cela m'a fait réfléchir ... Je me demandais si les ordinateurs quantiques pouvaient être simulés efficacement par les ordinateurs classiques. Serait-ce...
IP = PSPACE est répertorié comme l'exemple canonique d'un résultat non relativisant, et la preuve en est qu'il existe un oracle OOO tel que , tandis que {\ sf coNP} ^ O \ subseteq {\ sf PSPACE} ^ O pour tous oracles O .c o N P O ⊆ P S P A C E O OcoNPO⊈IPOcoNPO⊈IPO{\sf coNP}^O \not\subseteq {\sf...
Il est bien connu que l'ensemble des langages ayant des systèmes de preuve interactifs à deux prouveurs, dans lesquels le vérificateur s'exécute en temps polynomial (MIP), est NEXP. Mais existe-t-il des limites connues sur la puissance de ces preuves interactives lorsque les prouveurs sont limités...
Le système de preuve probabiliste est communément appelé une restriction de , où Arthur ne peut utiliser que bits aléatoires et ne peut examiner que bits du certificat de preuve envoyé par Merlin (voir, http://en.wikipedia.org/wiki/Interactive_proof_system#PCP ).M A f ( n ) g ( n )PCP[ f( n ) , g(...
Préambule. La classe de complexité AM sont les problèmes qui peuvent être résolus par un système de preuve interactif à deux tours entre un prouveur "Merlin" et un vérificateur "Arthur". Un problème - qui teste certaines propriétés d'un objet X - est dans AM si: Pour les instances OUI , pour un...
Comment puis-je convaincre Coq que la fonction récursive donnée ci-dessous se termine? La fonction prend deux arguments inductifs. Intuitivement, la récursivité se termine car l'un ou l'autre argument est décomposé. Plus précisément, la fonction prend deux arbres en entrée. Inductive Tree := | Tip:...
Ma première question est de savoir si une caractérisation de système de preuve interactive est connue pour toutes les classes de complexité classiques. J'appellerais P, NP, PSPACE, EXP, NEXP, EXPSPACE, les fonctions récursives et récursivement énumérables (entre autres). Plus précisément, une...
Beigi, Shor et Watrous ont un très bon article sur la puissance des preuves interactives quantiques avec des messages courts. Ils considèrent trois variantes de «messages courts», et la seule qui m'importe est leur deuxième variante où un nombre illimité de messages peut être envoyé, mais la...
Le théorème de prétention parallèle de Raz est un résultat important dans le PCP, l'inapproximation, etc. Le théorème est fomalisé comme suit. Un jeu , où S , T , A , B sont des ensembles finis, π est une distribution sur S × T et un prédicat V : S × T × A × B → { 0 , 1 } . Définir la valeur du jeu...
Je lis dans SP Jordan, D. Gosset, "PJ amour des problèmes COMPLETES pour Hamiltonians stoquastic et matrices de MarkovQ MUNEQMAQMA " qu'il est peu probable que .Q MA ⊆ A MQMA⊆AMQMA \subseteq AM J'ai été surpris de cette affirmation. Quelle est donc la bonne relation entre et A M ?Q MUNEQMAQMAA...
Merlin, qui a des ressources informatiques illimitées, veut convaincre Arthur que m|∑p≤N, p primepkm|∑p≤N, p primepkm|\sum_{p\le N,\ p\text{ prime}}p^k pour (N,m,k)(N,m,k)(N,m,k) avec k=O(logN)k=O(logN)k=O(\log N) et m=O(N).m=O(N).m=O(N). Le calcul simple de cette somme (exponentiation modulaire...
L'exhaustivité et la solidité des systèmes de preuve interactifs sont définies de manière informelle comme: Exhaustivité: Si une déclaration est vrai, l' honnête prouveur peut convaincre l' honnête vérificateur de ce fait PVT . Solidité: si une déclaration est fausse, le prouveur de fraude ne peut...
J'ai récemment appris les preuves interactives et je me demandais si le tout n'était rien de plus qu'une curiosité théorique, ou s'il avait des applications pratiques. J'ai pensé commencer par un exemple qui m'est venu sous la douche: Ces derniers temps, la nouvelle a été que "Nombre de Dieu" = 20....
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...
Dans la plupart des systèmes de preuve probabilistes (théorème PCP, par exemple), les probabilités d'erreur sont généralement définies du côté des faux positifs, c'est-à-dire qu'une définition typique pourrait ressembler à: si alors le vérificateur accepte toujours, mais dans les autres cas, la...
Définissez le modèle de calcul MPostBQP comme étant identique à PostBQP, sauf que nous autorisons de nombreuses mesures de qubit polynomiales avant la post-sélection et la mesure finale. Pouvons-nous fournir des preuves indiquant que MPostBQP est plus puissant que PostBQP? Définissez MPostBQP [k]...
IP (2pfa) et AM (2pfa) sont les classes de langues reconnues avec erreur bornée par les versions de pièces privées et publiques, respectivement, des systèmes de preuve interactifs avec des vérificateurs qui sont des automates finis probabilistes avec une tête d'entrée bidirectionnelle. Des...