Questions marquées «oracles»

Définir ioioio - SUBEXPSUBEXPSUBEXP comme étant la classe de langues LLL telle qu'il existe une langue L′∈∩ε>0TIME(2nε)L′∈∩ε>0TIME(2nε)L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}}) et pour une infinité de nnn , LLL et L′L′L' accord sur toutes les instances de longueur nnn ....

Dans de nombreux domaines, il existe des techniques canoniques que tous ceux qui travaillent dans le domaine devraient maîtriser. Par exemple, pour les réductions d'espace de journalisation, le "truc de bit" pour la composition consiste à ne pas construire la sortie complète de la fonction...

En général, la bande de requête d'un oracle compte pour la complexité spatiale d'une MT. Cependant, il semble plausible d'autoriser une bande oracle en écriture seule (comme celle utilisée dans les réductions d'espace L). Une telle construction est-elle utile? Cela donne-t-il des résultats...

Eh bien, le titre dit à peu près tout. La question intéressante ci-dessus a été posée par le commentateur Jay sur mon blog (voir ici et ici ). J'imagine à la fois que la réponse est oui et qu'il existe une preuve relativement simple, mais je ne pouvais pas la voir à la légère. (Très grossièrement,...

Supposons que soit un arbre à degrés constants dont nous ne connaissons pas la structure. Le problème est de sortir l'arbre en posant des requêtes de la forme: "Le nœud se trouve-t-il sur le chemin du nœud au nœud ?". Supposons que chaque requête puisse recevoir une réponse en temps constant par un...

Je viens de lire la question " La factorisation des nombres entiers est-elle un problème NP-complet? " ... alors j'ai décidé de dépenser une partie de ma réputation :-) en posant une autre question ayant :P ( Q est trivial ) ≈ 1QQQP( Q est trivial ) ≈ 1P(Q est trivial)≈1P(\text{Q is trivial})...

Contexte Il est connu qu'il existe un oracle AAA de telle sorte que, P S P A C E A ≠ P H APSPACEA≠PHAPSPACE^A \neq PH^A . On sait même que la séparation tient par rapport à un oracle aléatoire. De manière informelle, on peut interpréter cela comme signifiant qu'il existe de nombreux oracles pour...

Dans "Quantum Computation and Quantum Information" de Mike et Ike, l'algorithme de Grover est expliqué en détail. Cependant, dans le livre, et dans toutes les explications que j'ai trouvées en ligne pour l'algorithme de Grover, il ne semble pas y avoir de mention de la façon dont l'Oracle de Grover...

La façon la plus courante dans laquelle les oracles se produisent dans la théorie de la complexité est la suivante: un oracle fixe est mis à la disposition, par exemple, d'une machine de Turing avec certaines ressources limitées, et on étudie comment l'oracle augmente la puissance de calcul de la...

Dans un article intitulé «Sur le déni dans la chaîne de référence commune et le modèle Oracle aléatoire», Rafael Pass écrit: Nous notons que lors de la démonstration de la sécurité selon la définition standard de la connaissance zéro dans le modèle RO [Oracle aléatoire], le simulateur a deux...

En termes simples: quelle est la correspondance entre les machines de Turing avec oracles et les familles de circuits uniformes avec oracles? Comment ces derniers sont-ils définis afin d'obtenir le même modèle de calcul, pour une machine Oracle Turing donnée? Cela peut être une question...

Par http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf Si est un langage complet-PSPACE, P A = N P A .UNEAAPUNE= NPUNEPA=NPAP^{A}=NP^{A} Si est un oracle à temps polynomial déterministe, P B ≠ N P B (en supposant P ≠ N P ).BBBPB≠ NPBPB≠NPBP^{B}\ne NP^{B}P≠ NPP≠NPP\ne NP est la classe de...

Est-ce que NPNP∩coNP=NPNPNP∩coNP=NP\mathsf{NP^{NP \,\cap\, coNP}=NP}maintenez? Clairement NPNP≠NPNPNP≠NP\mathsf{NP^{NP}\neq NP} , mais il me semble que NP∩coNPNP∩coNP\mathsf{NP\cap coNP} est "déterministe" ce qui me fait croire que c'est vrai. Existe-t-il une preuve simple (ou peut-être juste par...

Il est bien connu que le problème d'arrêt n'est pas calculable. Cependant, il est possible de "compresser" exponentiellement des informations sur le problème d'arrêt, de sorte que sa décompression soit calculable. Plus précisément, il est possible de calculer à partir d'une description de machines...

Cette question peut avoir une réponse évidente ... mais voici la question de toute façon. Intuitivement, c'est la déclaration plausible suivante - "une machine avec un sous-programme A qui à son tour a un sous-programme B est la même chose qu'une machine avec un sous-programme A qui a accès au...

NL⊈PNL⊈P\mathsf{NL} \nsubseteq \mathsf{P} Considérons maintenant familles de circuits avec portes d'oracle - disons, , où A est une classe complexe de circuit contenant logspace avec accès oracle à une autre classe B , par des portes d'oracle annexés à la base de A . Existe-t-il des exemples...

Je voudrais savoir s'il existe un monde relativisée où . Je suis également intéressé à savoir s'il existe un monde relativisée où P B ≠ N P B = P P B .PUNE= N PUNE≠ P PUNEPA=NPA≠PPA{\bf P^A}={\bf NP^A}\not = {\bf PP^A}PB≠ N PB= P PBPB≠NPB=PPB{\bf P^B} \not = {\bf NP^B} = {\bf...

Les générateurs invulnérables sont définis comme suit: Soit une relation NP, et M une machine qui accepte L ( R ) . Informellement, un programme est un générateur invulnérable si, sur l'entrée 1 n , il produit des paires instance-témoin ( x , w ) ∈ R , avec | x | = N , selon une répartition en...

Soit tout problème complet d'EXP. Ensuite, P A = N P A .AAAPA=NPAPA=NPAP^A = NP^A Que soit un oracle qui prend en compte les requêtes que M (un TM en P) fera, et nous pouvons obtenir P B ≠ N P B .BBBMMMPB≠NPBPB≠NPBP^B \neq NP^B Question: Avons-nous des résultats oracle similaires pour P vs...

Je n'ai pas pu trouver de déclaration reliant M AMA\mathsf{MA} et N PR PNPRP\mathsf{NP}^\mathsf{RP} dans la littérature; des pointeurs seraient appréciés. Je pense qu'ils sont égaux: M A ⊆ N PR PMA⊆NPRP\mathsf{MA} \subseteq \mathsf{NP}^\mathsf{RP} : LamachineN PNP\mathsf{NP} devine la chaîne de...