L'intuizione dietro Relativizzazione

Question

Prendo corso sulla complessità computazionale. Il mio problema è che non capisco metodo Relativizzazione . Ho cercato di trovare un po 'di intuizione in molti libri di testo, purtroppo, finora senza successo. Io apprezzo se qualcuno potrebbe gettare la luce su questo argomento in modo che sarò in grado di continuare da solo. Poche frasi seguenti sono domande e le mie riflessioni su relativizzazione, che vi aiuterà a navigare la discussione.

Molto spesso relativizzazione viene a confronto con diagonalizzazione, che è un metodo che aiuta a distinguere tra insieme numerabile e insieme non numerabile. Si tratta in qualche modo dalla relativizzazione che $ P $ contro $ NP $ questione non può essere risolto con diagonalizzazione. Io non vedo proprio l'idea del perché relativizzazione mostrano l'inutile di diagonalizzazione, e se è inutile perché è in realtà inutile.

L'idea alla base della macchina di Turing oracolo $ M ^ A $ in un primo momento è molto chiaro. Tuttavia, quando si tratta di $ NP ^ A $ e $ P ^ A $ i scompare intuizione. Oracle è un convertitore che è stato progettato per lingua speciale e risponde alla domanda se la stringa sull'ingresso del oracolo nella lingua in tempo 1. Come ho capito TM che contiene un oracolo è solo fare alcune operazioni ausiliarie e chiedere l'oracolo. Così il nucleo del TM è l'oracolo, tutto il resto è meno importante. Qual è la differenza tra $ P ^ A $ e $ NP ^ A $, anche pensato di Oracle in ciascuno di essi funziona in tempo 1.

L'ultima cosa è la prova dell'esistenza di un oracolo $ B $ tale che $ P ^ B \ neq NP ^ B $. Ho trovato la prova in diversi libri di testo e in ognuno di essi la prova sembra molto vaga. Ho cercato di usare "Introduzione alla complessità" di Sipser, Chapter9. Intrattabilità , e non ha ottenuto l'idea di costruzione di un elenco di tutti i tempi polinomiale oracolo TM $ m_i $.

Questo è più o meno tutto quello che so di relativizzazione, mi apprezzerà se someonw avrebbe deciso di condividere le sue / suoi pensieri sul tema.

Addendum : in uno dei libri di testo che ho trovato esempio di $ NP ^ B $ lingua (complessità computazionale: Approccio A Modern da Boaz Barak Sanjeev Arora Teorema 3.7 Page 74..). $ U_B = \ left \ {1 ^ n: alcuni \ spazio di stringa \ spazio di \ lunghezza spazio \ nr \ lo spazio è \ spazio \ spazio B \ right \} $ è il linguaggio unario. Credo che (1,11,111,1111, ...) sono tutti in $ U_B $. Autore afferma che un tale linguaggio è in $ NP ^ B $ che è non riesco a capire il motivo per cui, da qui Oracle per B può risolvere tutto in tempo 1. Perché abbiamo bisogno di TM non deterministica con Oracle. Se non è un buon esempio di $ NP ^ B $ si prega di mettere il vostro in modo tale che per approvare l'esistenza di $ NP ^ B $.

Answer 1

Non hai veramente chiesto a qualsiasi domanda, ma sembra che non si sa che cosa $ \ rm {P} ^ a $ mezzi e quali $ \ rm {NP} ^ a $ mezzi per un linguaggio di $ A $ . La classe $ \ rm {NP} ^ A $ è semplicemente tutte le lingue che sono decidibile in "tempo NP", data una macchina di Turing con $ A $ come un oracolo. Ciò significa che una macchina di Turing non deterministica con accesso a $ A $ che viene eseguito in tempo polinomiale. Il rm $ \ {P} ^ A $ è la versione deterministica.