Intuition derrière la relativisation

Je prends un cours sur la complexité informatique. Mon problème est que je ne comprends pas la méthode de relativisation . J'ai essayé de trouver un peu d'intuition dans de nombreux manuels, malheureusement, jusqu'à présent sans succès. J'apprécierai que quelqu'un puisse faire la lumière sur ce sujet afin que je puisse continuer par moi-même. Peu de phrases suivantes sont des questions et mes réflexions sur la relativisation, elles aideront à naviguer dans la discussion.

Très souvent, la relativisation vient en comparaison avec la diagonalisation, qui est une méthode qui permet de distinguer l'ensemble dénombrable de l'ensemble dénombrable. Il vient en quelque sorte de la relativisation que la question versus ne peut pas être résolue par diagonalisation. Je ne vois pas vraiment pourquoi la relativisation montre l'inutile de la diagonalisation, et si elle est inutile, pourquoi est-elle réellement inutile.$P$$NP$

L'idée derrière l'oracle Turing machine au début est très claire. Cependant, en ce qui concerne et l'intuition disparaît. Oracle est une boîte noire qui est conçue pour un langage spécial et répond à la question de savoir si la chaîne à l'entrée de l'oracle est dans la langue dans le temps 1. Comme je l'ai compris, TM qui contient un oracle consiste simplement à effectuer des opérations auxiliaires et à demander à l'oracle. Donc, le noyau de la MT est l'oracle, tout le reste est moins important. Quelle est la différence entre et , même l'oracle pensé dans les deux fonctionne dans le temps 1.$M^A$$NP^A$$P^A$$P^A$$NP^A$

La dernière chose est la preuve de l'existence d'un oracle tel que . J'ai trouvé la preuve dans plusieurs manuels et dans chacun d'eux, la preuve semble très vague. J'ai essayé d'utiliser "Introduction à la complexité" par Sipser, Chapter9. Intractabilité , et n'a pas eu l'idée de construire une liste de toutes les MT oracle temporelles polynomiales .$B$$P^B \neq NP^B$$M_i$

C'est plus ou moins tout ce que je sais sur la relativisation, j'apprécierai si quelqu'un décide de partager ses réflexions sur le sujet.

Addendum : dans l'un des manuels, j'ai trouvé un exemple de langage (Complexité informatique: une approche moderne de Boaz Barak Sanjeev Arora. Théorème 3.7. Page 74). c'est un langage unaire. Je crois que (1,11,111,1111, ...) sont tous dans . L'auteur affirme qu'un tel langage est en c'est-à-dire que je ne peux pas comprendre pourquoi, donc l'oracle pour B peut tout résoudre dans le temps 1. Pourquoi avons-nous besoin d'une MT non déterministe avec oracle. Si ce n'est pas bon exemple de s'il vous plaît mettre le vôtre de telle sorte que pour approuver l'existence de .$NP^B$$U_B=\left \{ 1^n:some \space string \space of \space length \space n \space is \space in \space B\right \}$$U_B$$NP^B$$NP^B$$NP^B$

Vous ne l' avez pas vraiment posé une question, mais il semble que vous ne savez pas ce que moyen et que moyen pour une langue . La classe est simplement tous les langages décidables en "temps NP", étant donné une machine de turing avec comme oracle. Cela signifie une machine de turing non déterministe avec accès à qui fonctionne en temps polynomial. Le est la version déterministe.$\rm{P}^A$$\rm{NP}^A$$A$$\rm{NP}^A$$A$$A$$\rm{P}^A$