ограниченные в пространстве ТМ и оракулы

20

В общем, лента запросов для оракула учитывает сложность пространства ТМ. Тем не менее, кажется правдоподобным разрешить запись оракула только для записи (например, которая используется в сокращениях L-пространства).

Полезна ли такая конструкция? Дает ли он какие-то особенно абсурдные результаты?

cc.complexity-theory space-bounded oracles Джереми Хурвиц
источник

Если у вас есть TM с записью Oracle только для записи, как вы прочитаете ответ? Тогда вы можете просто забыть о оракуле.

Маркос Вильягра

1

Существуют деликатные проблемы при выборе правильного определения доступа оракула для машин, ограниченных пространством. См. «Релятивизация классов малой сложности и их теории» Клауса Элига, Стивена Кука и Фуонга Нгуена, CSL 2007.

Каве

@Marcos: Я считаю, что ответ - это просто внутреннее состояние машины, а не запись на ленту оракула.

Джо Фицсимонс

Какова ссылка на это определение космических машин-оракулов?

Мифорбес

10

Я думаю, что один удивительный факт заключается в том, что в этой модели теорема Савича не «явно» релятивизируется. То есть можно видеть, что и в этой модели, и в настоящее время мы не знаем, что (и теорема Савича в этом контексте, похоже, не дает этого). Я был бы заинтересован в том, может ли это быть "доказуемо" нерелятивизирующим. $PSPACE^P=EXPTIME$ $NPSPACE^P=NEXPTIME$ $EXPTIME=NEXPTIME$

Можно также заметить, что в этой модели. $NL^{NL}=NL^L=NP$

Тем не менее, я думаю, что об этой модели, по крайней мере, стоит подумать в отношении вопросов релятивизации в теореме о пространственной иерархии. Кроме того , в некотором смысле, я хочу сделать поли размером запросов к . $L^A$ $A$

miforbes
источник

1

Я забыл одну вещь: как NL = coNL, мы должны хотеть NL ^ NL = NL, но ясно, что если в этой модели NL ^ NL = NP, мы не можем использовать NL = coNL, чтобы свернуть "иерархию NL". В другом представлении о оракулах, ограниченных пространством, иерархия действительно рушится (ссылки см. В статье Иммермана NL = coNL).

Мифорбес

У вас есть ссылка? Я ожидал бы

. Действительно, пусть

будет рекурсивно перечислимым языком,

TM, который распознает

и

TM, который читает вход и число

равное «1», а затем моделирует

для этого ввода на

шагов. Затем, не используя пробела, я мог бы скопировать данные на ленте оракула, угадать необходимое число 1 и запросить

.

N S P A C E (0)^{P} = R E

$\rm{NSPACE(0)^P=RE}$

L

$L$

M

$M$

L

$L$

M^{'}

$M'$

n

$n$

M

$M$

n

$n$

M^{'}

$M'$

Артур МИЛЬЧИОР

9

Это может не ответить на ваш вопрос (который, честно говоря, я не до конца понимаю), но я думаю, что это в том же духе. Известно, что есть разница в сводимости между logspace TM с одной оракульной лентой и одной с доступом к нескольким оракульным лентам. Кроме того, следующее понятие пространства журналов обладает хорошими свойствами: TM может использовать только объем журнала на своей рабочей ленте, но он может использовать объем пространства полинома на своих лентах оракула.

Ссылка: http://groups.csail.mit.edu/tds/papers/Lynch/tcs78.pdf

Аарон Стерлинг
источник

3

NSPACE (0) P = RE, что, я думаю, немного абсурдно.

Действительно, пусть L будет рекурсивно перечислимым языком, M TM, который распознает L и M ′ TM, который читает вход и число n, равное «1», а затем моделирует M для этого ввода на n шагов. Затем, не используя пробела, я мог бы скопировать данные на ленте оракула, угадать необходимое число 1 и запросить M ′.

Тогда M 'примет, если M примет, и будет достаточно большой вход, чтобы быть полиномиальным.

Артур МИЛКИОР
источник

ограниченные в пространстве ТМ и оракулы

Ответы: