est

8

Je pense que ces deux classes devraient être les mêmes, mais je ne trouve aucune littérature à ce sujet et j'ai une formation limitée sur le sujet.

C'est mon raisonnement, et je voudrais savoir si (1) cela est déjà connu ou (2) j'ai mal compris quelque chose ou (3) je viens de découvrir quelque chose d'utile:

PCTC est la classe de problèmes qui peuvent être résolus en mettant des quantités polynomiales de données dans une machine à remonter le temps.

BPPpath est la classe de problèmes qui peuvent être résolus par la post-sélection dans une machine de Turing probabiliste, c'est-à-dire en ignorant les cas qui ne vous intéressent pas.

PCTC⊆BPPpathcar vous pouvez simuler une courbe temporelle fermée avec une post-sélection comme celle-ci: Scannez tout le programme au début, à la fois l'état et la mémoire. Ensuite, après le traitement, faites-le à nouveau et sélectionnez-le de manière à ce que vous ne retourniez que si l'état et la mémoire sont maintenant exactement égaux à l'état de démarrage et à la mémoire (à l'exception d'un seul bit qui indique s'il s'agit ou non de la première itération, pour empêcher une boucle infinie).

BPPpath⊆PCTC car vous pouvez simuler une post-sélection comme celle-ci: si le message du futur commence par 1, envoyez le message 0dans le passé. Sinon, procédez comme d'habitude. Lorsque vous arrivez à l'étape où vous effectuez normalement une post-sélection, envoyez un 1 dans le passé. vous voulez ignorer cette chronologie, sinon un0. La seule version cohérente est maintenant celle où vous recevez et envoyez un 0 car vous êtes satisfait des résultats.

complexity-theory complexity-classes quantum-computing Florian Dietz
la source
2
Je n'ai absolument aucune idée de ce sujet, mais, dans ce lien papier , ils disent que la classe P_CTC est égale à PSPACE et BPP_PATH est égale à POST_BPP qui est contenu dans P avec un oracle NP. Donc, les deux classes ne sont probablement pas les mêmes
rotia
C'est bon à savoir! Je ne dirais pas que cela montre que les deux classes ne sont pas identiques, cependant: cela signifie simplement que si elles sont identiques, alors PSPACE = P ^ NP. Cela le rend moins vraisemblable car quelqu'un d'autre aurait pu découvrir cette connexion plus tôt si elle était vraie, mais cela signifie également que l'approche SI EST correcte, alors cela aura des conséquences utiles.
Florian Dietz
Le croquis de votre preuve que "P_CTC est dans BPP_PATH" est le coupable à mon avis. Un problème est qu'il n'est pas évident de savoir comment votre machine postBPP conserve correctement les états cohérents du nombre polynomial de registres CTC. P_CTC n'est pas simplement un temps polynomial avec un voyage dans le temps. Il existe des critères de cohérence causale très spécifiques qui doivent être appliqués. Ces contraintes permettent à la machine de trouver facilement des points fixes partiels, ce qui est sans doute plus général qu'une simple post-sélection. Je vous encourage à revoir attentivement la définition formelle de P_CTC.
mdxn

Réponses:

0

Je pense avoir trouvé la réponse: la preuve est fausse. BPP_PATH n'est pas dans P_CTC car P_CTC est requis pour donner une réponse définitive unique, tandis que BPP_PATH est un algorithme probabiliste, donc la deuxième réduction ne fonctionne pas. Pour que cela fonctionne, il faudrait utiliser les informations de voyage dans le temps pour compter le nombre de succès de l'algorithme probabiliste par rapport au nombre de ses échecs. Je n'ai aucune idée de comment faire cela, ou si cela peut même être fait (probablement pas).

Florian Dietz
la source
... et cinq minutes plus tard, je ne suis plus sûr. P_CTC = PSPACE, et PSPACE ne peut-il pas simuler BPP?
Florian Dietz
2
Vous vous embrouillez. Les machines déterministes sont essentiellement des machines probabilistes avec une tolérance zéro aux erreurs et aucun accès au hasard. Si une machine candidate peut répondre aux mêmes questions sans l'erreur, il n'y a pas de problème. Il n'est pas nécessaire de se tromper aussi souvent. Quoi qu'il en soit, PSPACE vous permet de simuler facilement une machine BPP en étant capable de tester chaque chaîne aléatoire et de calculer manuellement la probabilité d'acceptation. Puisque P_CTC = PSPACE, cela explique qu'il existe une machine P_CTC équivalente qui peut répondre de la même manière pour n'importe quelle machine BPP particulière.
mdxn