Этот вопрос может иметь очевидный ответ ... но вот вопрос в любом случае. Интуитивно понятно, что это следующее правдоподобное утверждение - «машина с подпрограммой A, которая в свою очередь имеет подпрограмму B, такая же, как машина с подпрограммой A, у которой есть доступ к подпрограмме B».
Чтобы определить эту проблему формально, я буду использовать некоторые нетрадиционные обозначения. Когда я говорю , я даю оракулу для проблемы . например, . С помощью этой «новой» записи можно определить и т. Д. Мой вопрос A B - C o m p l e t e N P N P = N P S A T = Σ 2 A B C
- это правильный способ думать о оракулах?
- есть
Например,
Я не могу придумать каких-либо очевидных контрпримеров к этому правилу. Кто-нибудь?
complexity-classes
oracles
gabgoh
источник
источник
Ответы:
Как сказал Venkat в комментариях, вам трудно понять ваше определение оракула, которое не определено как некоторая характеристика машины.
Пусть будет множеством TM в A с оракулом, который является машиной в ( B с оракулом в машине в C ). Очевидно , что машина А может позвонить C : он просто вызывает машину в B и просит его , чтобы нести сообщение непосредственно C .A(BC) A B C A C B C
Я предполагаю, что будет машиной в A, которая может вызывать оракула в C, или оракулом (машиной в B, которая может вызывать машину в C ), так что это точно такое же определение.( АВ)С A С В С
Наконец, вы можете захотеть , который, безусловно, отличается от двух других (просто возьмите B = C = N P и A = P , затем A B , C = N P ∪ c o N P, тогда как A ( B C ) = Σ P 2 ∪ Π p 2 .AB , C B = C= Nп A = P AB , C= Nп∪coNP A(BC)=ΣP2∪Πp2
источник
Я написал бы следующее как комментарий, но это было слишком долго, чтобы соответствовать.
Давайте сначала опишем значение «алгоритмов в классе с оракулом для языка A.» (На это указал Цуёси Ито). Мы будем использовать то же соглашение, которое использовали Ладнер и Линч . Соглашение хорошо описано Bennett & Gill :C
Стандартное определение классов сложности машин-оракулов следующее: Пусть B и C - классы сложности . Тогда является законным класс сложности, определяется как X = ⋃ L ∈ C B L . Здесь B L представляет класс сложности решений задач, решаемых алгоритмом в классе B с оракулом для языка L.X=BC X=⋃L∈CBL BL
Так как X является законным классом сложности, для любого класса сложности А, можно говорить о классах сложности и X A = ( B C ) A .AX=A(BC) XA=(BC)A
относится к классу сложности задачрешаемых решения алгоритма в классе А с оракулом для любого языка L ' ∈ X = ⋃ L ∈ C B L . Другими словами, A X = ⋃ L ′ ∈ { ⋃ L ∈ C B L } A L ′ .AX L′∈X=⋃L∈CBL AX=⋃L′∈{⋃L∈CBL}AL′
относится к классу сложности задачрешаемых решения алгоритма в классе X = ⋃ L ∈ C B L с оракулом для любого языка L ' ∈ A . Другими словами, X A = ⋃ L ′ ∈ A X L ′ = ⋃ L ′ ∈ A ( ⋃ L ∈ C B L ) L ′ .XA X=⋃L∈CBL L′∈A XA=⋃L′∈AXL′=⋃L′∈A(⋃L∈CBL)L′
Утверждение: .(BL1)L′∪(BL2)L′=(BL′)L1∪L2
Side Note: Since it's 3:00 AM now, I'm too sleepy to check the validity of the above claim! I think it's valid & elementary to prove, yet it's nice to see the actual proof.
Таким образом, можно записать .XA=⋃L′∈A(⋃L∈CBL)L′=⋃L∈C,L′∈A(BL′)L
пример
Пусть . Мы знаем , что C уплотнительное N P ⊆ X . Предоставление как доступ стороны оракула к N P , один получает: с о N P N P ⊆ X N P = ( P N P ) N P .X=PNP coNP⊆X NP coNPNP⊆XNP=(PNP)NP
эпилог
Плодотворная дискуссия с Цуёси Ито показала (для меня), что нелегко вдвойне релятивизировать класс сложности. На самом деле, даже определение одного кажется проблематичным. Я должен определенно учиться больше, чтобы видеть, дается ли когда-нибудь удовлетворительное определение. Между тем, я ценю любые комментарии, которые могут быть использованы для решения этой проблемы.
источник