Являются ли оракулы ассоциативными?

11

Этот вопрос может иметь очевидный ответ ... но вот вопрос в любом случае. Интуитивно понятно, что это следующее правдоподобное утверждение - «машина с подпрограммой 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 CABABCompleteNPNP=NPSAT=Σ2ABC

  • это правильный способ думать о оракулах?
  • есть(AB)C=A(BC)

Например,(NпNп)Nпзнак равноΣ2Nпзнак равноNпΣ2знак равноNп(NпNп)

Я не могу придумать каких-либо очевидных контрпримеров к этому правилу. Кто-нибудь?

gabgoh
источник
Вы видели мой вопрос: cstheory.stackexchange.com/q/972/873 ?
MS Dousti
1
это немного более общий вопрос, но вопрос Садека весьма актуален, и особенно комментарии о плохо сформированности A ^ B ^ C, если A ^ B не является вычислительной моделью
Суреш Венкат
нет, но это было именно то, что я ударил головой о стену прошлой ночью, из-за чего и возник этот вопрос!
Габго
Также посмотрите этот вопрос .
Каве

Ответы:

5

Как сказал Venkat в комментариях, вам трудно понять ваше определение оракула, которое не определено как некоторая характеристика машины.

Пусть будет множеством TM в A с оракулом, который является машиной в ( B с оракулом в машине в C ). Очевидно , что машина А может позвонить C : он просто вызывает машину в B и просит его , чтобы нести сообщение непосредственно C .A(ВС)AВСAСВС

Я предполагаю, что будет машиной в A, которая может вызывать оракула в C, или оракулом (машиной в B, которая может вызывать машину в C ), так что это точно такое же определение.(AВ)СAСВС

Наконец, вы можете захотеть , который, безусловно, отличается от двух других (просто возьмите B = C = N P и A = P , затем A B , C = N P c o N P, тогда как A ( B C ) = Σ P 2Π p 2 .AВ,СВзнак равноСзнак равноNпAзнак равнопAB,C=NPcoNPA(BC)=Σ2PΠ2p

Артур МИЛКИОР
источник
4
Будьте осторожны: P ^ NP включает NP∪coNP, но он не известен или не считается равным NP∪coNP. Точно так же P ^ (NP ^ NP), как известно, не равен Σ2P∪Π2P.
Цуёси Ито
1
@ Tsuyoshi, спасибо за замечание, я не знаю, почему я так подумал. В самом деле , если , ясно , что Р Н Р . Пусть и Б быть проблемы NPcomplte и coNPcomplete, то проблема , которую принимают входной сигнал ( х , у ) и ответить верно , если х и у B в P N P , но не в N P гр ö N P . NPcoNPPNPAB(x,y)xAyBPNPNPcoNP
Артур МИЛЬЧИОР
3

Я написал бы следующее как комментарий, но это было слишком долго, чтобы соответствовать.

Давайте сначала опишем значение «алгоритмов в классе с оракулом для языка A.» (На это указал Цуёси Ито). Мы будем использовать то же соглашение, которое использовали Ладнер и Линч . Соглашение хорошо описано Bennett & Gill :C

могут быть определены различными способами, в зависимости от того, как обрабатывается лента запроса. Мы следуем соглашениям Ladner и Lynch [LL]: лента запроса не взимается с пробела, но, чтобы не использовать его как рабочую ленту, лента запроса односторонняя и доступна только для записи и стирается автоматически после каждого запроса. (Саймон [Si] рассматривает ленту запросов как одну из рабочих лент, ленту двустороннего чтения / записи, которая заряжается на ограниченном пространстве. Определение Ладнера-Линча является менее ограничительным и, возможно, более естественным, поскольку для случайного оракулаA L O G S P A C E ALOGSPACEAALOGSPACEA выполняется с вероятностью 1 для [LL], но не для [Si])

[LL] RE LADNER, NA LYNCH, Релятивизация вопросов о вычислимости лог-пространства , Матем. Теория систем, 10 (1976), с. 19-32.

[Si] Дж. Симон, О некоторых центральных проблемах в вычислительной сложности , Tech. Реп ТР 75-224, кафедра компьютерных наук, Корнельский университет, Итака, Нью-Йорк, 1975.

Стандартное определение классов сложности машин-оракулов следующее: Пусть B и C - классы сложности . Тогда является законным класс сложности, определяется как X = L C B L . Здесь B L представляет класс сложности решений задач, решаемых алгоритмом в классе B с оракулом для языка L.X=BCX=LCBLBL

Так как 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 .AXLX=LCBLAX=L{LCBL}AL

  • относится к классу сложности задачрешаемых решения алгоритма в классе X = L C B L с оракулом для любого языка L 'A . Другими словами, X A = L A X L = L A ( L C B L ) L .XAX=LCBLLAXA=LAXL=LA(LCBL)L

Утверждение: .(BL1)L(BL2)L=(BL)L1L2

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=LA(LCBL)L=LC,LA(BL)L

пример

Пусть . Мы знаем , что C уплотнительное N PX . Предоставление как доступ стороны оракула к N P , один получает: с о N P N PX N P = ( P N P ) N P .X=PNPcoNPXNPcoNPNPXNP=(PNP)NP

эпилог

Плодотворная дискуссия с Цуёси Ито показала (для меня), что нелегко вдвойне релятивизировать класс сложности. На самом деле, даже определение одного кажется проблематичным. Я должен определенно учиться больше, чтобы видеть, дается ли когда-нибудь удовлетворительное определение. Между тем, я ценю любые комментарии, которые могут быть использованы для решения этой проблемы.

М.С. Дусти
источник
4
Как я прокомментировал другой вопрос , «алгоритм в классе B с оракулом для языка L» вообще не имеет общепринятого определения.
Цуёси Ито
@Tsuyoshi: я отредактировал ответ, чтобы представить, какое определение я использую. Удаляет ли это плохо сформированное?
MS Dousti
Нет. Добавленная часть определяет только то, что означает LOGSPACE ^ A, а не то, что B ^ A означает для чего-то вроде B = NP ^ NP.
Цуёси Ито
@ Цуйоши: Спасибо. Я просто добавил пример, чтобы уточнить, что я имею в виду. Я хочу такое определение, что если , то A CX C (очень естественное требование). Можете ли вы помочь мне понять, как это должно быть определено, когда X - класс оракула, такой как NP ^ NP? AXACXC
MS Dousti
4
К сожалению, ваше «естественное требование» на самом деле не так естественно. Хотя PSPACE⊆IP и существует естественное и общепринятое определение IP ^ A для любого языка A (верификатору предоставляется оракульный доступ к A), известно, что PSPACE ^ A⊈IP ^ A с вероятностью 1 для случайного оракул А; см. Чанг, Чор, Гольдрайх, Хартманис, Хостад, Ранджан и Рохатги 1994 . Как я уже говорил, не существует общепринятого определения C ^ A для произвольного класса сложности C, насколько я знаю. (подробнее)
Цуёси Ито