Intuitivement relativisation

Question

Je prends cours sur la complexité informatique. Mon problème est que je ne comprends pas méthode relativisation . J'ai essayé de trouver un peu d'intuition dans de nombreux manuels, malheureusement, jusqu'à présent sans succès. Je vais apprécier si quelqu'un pourrait jeter la lumière sur ce sujet afin que je serai en mesure de continuer moi-même. Quelques phrases suivantes sont des questions et mes pensées au sujet de relativisation, ils aident à naviguer dans la discussion.

Très souvent relativisation est en comparaison avec diagonalisation, qui est une méthode qui permet de distinguer entre dénombrable et ensemble indénombrable. Il est en quelque sorte de relativisation que $ P $ par rapport à la question $ NP $ ne peut être résolu par diagonalisation. Je ne vois vraiment pas pourquoi l'idée relativisation montrer l'inutile de diagonalisation, et si elle est inutile pourquoi est en fait inutile.

L'idée d'abord derrière la machine de Turing oracle $ M ^ A $ est très claire. Cependant, quand il s'agit de $ NP ^ A $ et $ P ^ A $ l'intuition disparait. Oracle est une boîte noire qui est conçu pour la langue particulière et répond à la question de savoir si la chaîne sur l'entrée de l'oracle est dans la langue dans le temps 1. Comme je l'ai compris TM qui contient un oracle est de faire quelques-unes des opérations auxiliaires et demander l'oracle. Ainsi, le noyau de la TM est l'oracle, tout le reste est moins important. Quelle est la différence entre $ P ^ A $ et $ NP ^ A $, même pensé oracle dans les deux d'entre eux travaille dans le temps 1.

La dernière chose est la preuve de l'existence d'un oracle $ B $ tel que $ P ^ B \ NEQ NP ^ B $. J'ai trouvé la preuve dans plusieurs manuels scolaires et dans tous la preuve semble très vague. J'ai essayé d'utiliser « Introduction à la complexité » par Sipser, Chapitre9. Indocilité , et n'a pas eu l'idée de la construction d'une liste de tous oracle temps polynomial $ M_i $ TMs.

Ceci est plus ou moins tout ce que je sais relativisation, j'appréciera si someonw déciderait de partager ses / ses réflexions sur le sujet.

Addendum : dans l'un des manuels, j'ai trouvé par exemple de $ NP ^ B langage $ (Complexité: une approche moderne de Boaz Barak Sanjeev Arora Théorème 3.7 Page 74..). $ U_B = \ left \ {1 ^ n: un peu \ string espace \ espace de \ longueur de l'espace \ espace n \ espace est \ espace \ espace B \ right \} $ c'est la langue unaire. Je crois que (1,11,111,1111, ...) sont tous en $ U_B $. Auteur affirme que cette langue est en $ NP ^ B $, ce qui est je ne comprends pas pourquoi, d'où oracle B peut tout résoudre dans le temps 1. Pourquoi avons-nous besoin nondéterministe TM avec Oracle. Si ce n'est pas bon exemple de $ NP ^ B $ s'il vous plaît mettre le vôtre de telle sorte que d'approuver l'existence de $ NP ^ B $.

Answer 1

Vous avez pas vraiment posé une question, mais il semble que vous ne savez pas ce que $ \ rm {P} ^ Un moyen de $ et que $ \ rm {NP} ^ Un moyen de $ pour une langue $ A $ . La classe $ \ rm {NP} ^ A $ est tout simplement toutes les langues qui sont décidables dans "NP temps", étant donné une machine à turation avec $ A $ comme un oracle. Ce moyen d'une machine à turation non-déterministe avec accès à $ A $ qui fonctionne en temps polynomiale. Le $ \ rm {P} ^ A $ est la version déterministe.