Lorsque j'expliquais la preuve de Baker-Gill-Solovay qu'il existe un oracle avec lequel nous pouvons avoir, , et un oracle avec lequel nous pouvons avoir à un ami, une question s'est posée pour savoir pourquoi de telles techniques sont mal adaptées pour prouver le problème , et je n'ai pas pu...
Comment prouver que ? Je cherche juste un tel oracle TM et un langage récursif pour lequel cela vaut. ML(M)=LN PUNE≠ c o N PUNENPA≠coNPA\mathsf{NP}^A \neq \mathsf{coNP}^AMMML ( M) = LL(M)=LL(M) = L Je connais la preuve où vous montrez qu'il y a un oracle tel que et un oracle tel que . J'ai un...
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...