Une question récente de Huck Bennett demandant si la classe PH était contenue dans la classe PP, a reçu des réponses quelque peu contradictoires (tout à fait vrai, semble-t-il). D'un côté, plusieurs résultats Oracle ont été donnés, et de l'autre Scott a suggéré que la réponse était probablement...
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...
Existe-t-il des exemples de jouets qui fournissent des informations «essentielles» sur la compréhension des trois obstacles connus au problème P= NPP=NPP = NP - la relativisation, les preuves naturelles et
Je lisais le document d'Andrej Bauer Premiers pas dans la théorie de la calculabilité synthétique . Dans la conclusion, il note que Notre axiomatisation a sa limite: elle ne peut prouver aucun résultat dans la théorie de la calculabilité qui ne parvienne pas à se relativiser aux calculs oracle. En...
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...
Est-il possible de tester algorithmiquement si un nombre calculable est rationnel ou entier? En d'autres termes, serait-il possible pour une bibliothèque qui implémente des nombres calculables de fournir les fonctions isIntegerou isRational? Je suppose que ce n'est pas possible, et que cela est en...
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...
Quels sont quelques exemples de paires de classes de complexité et B telles queAAABBB on ne sait pas si , etA=BA=BA=B nous ne connaissons pas non plus de relativisations contradictoires (c'est-à-dire que nous ne connaissons pas les oracles et Q tels que A P = B P et A Q ≠ B Q )?PPPQQQAP=BPAP=BPA^P...
Le problème de maintenance des commandes (ou «maintien de l'ordre dans une liste») est de supporter les opérations: singleton: crée une liste avec un élément, lui renvoie un pointeur insertAfter: donné un pointeur sur un élément, insère un nouvel élément après, renvoyant un pointeur sur le nouvel...
Ceci fait suite à cette question et est lié à cette question de Shiva Kinali. Il semble que les preuves dans ces articles ( Allender , Caussinus-McKenzie-Therien-Vollmer , Koiran-Perifel ) utilisent des théorèmes de hiérarchie. Je veux savoir si les preuves sont des théorèmes de diagonalisation "...
Lance Fortnow a récemment affirmé que prouver L! = NP devrait être plus facile que prouver P! = NP : NP séparé de l'espace logarithmique. J'ai donné quatre approches dans une enquête pré-blog 2001 sur la diagonalisation (section 3), mais aucune n'a échoué. Cela devrait être beaucoup plus facile que...
Si je comprends bien, une preuve que P = NP ou P ≠ NP devrait être non relativisable (comme dans les oracles de la théorie de la récursivité). Cependant, presque toutes les preuves semblent être relativisables. Quels sont les bons exemples de preuves non relativisables, du type d'une preuve P = NP...
Est-il possible de démontrer qu'une phrase doit être formellement indépendante du fait qu'elle est non relativisante? En d'autres termes, existe-t-il des exemples de phrases dans la théorie de la calculabilité / complexité où il peut être démontré à la fois a) que toutes les preuves qui résolvent...
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...
Je ne me souviens pas d'avoir vu une séparation de classes non basée sur des résultats de diagonalisation et de relativisation. La diagonalisation pourrait toujours être utilisée pour séparer les classes connues restantes, car des arguments non relativisants pourraient toujours être utilisés dans...
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...
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...
J'ai pensé à la question suivante à plusieurs reprises depuis que j'ai vu cette question sur la cryptographie . Question Soit une relation TFNP . Un oracle aléatoire peut-il aider P / poly à casser avec une probabilité non négligeable? Plus formellement, \ newcommand {\ Pr} {\ operatorname {Pr}} \...