kosmiczne bazy TM i wyrocznie

20

Zasadniczo taśma zapytania dla wyroczni liczy się do złożoności przestrzennej bazy TM. Wydaje się jednak prawdopodobne, aby zezwolić na taśmę Oracle tylko do zapisu (na przykład w przypadku redukcji przestrzeni L).

Czy taka konstrukcja jest przydatna? Czy przynosi jakieś absurdalne wyniki?

cc.complexity-theory space-bounded oracles Jeremy Hurwitz
źródło

Jeśli masz TM z taśmą Oracle tylko do zapisu, w jaki sposób przeczytasz odpowiedź? Wtedy możesz po prostu zapomnieć o wyroczni.

Marcos Villagra,

1

Istnieją delikatne kwestie przy podejmowaniu decyzji o właściwej definicji dostępu do Oracle dla maszyn ograniczonych przestrzenią. Patrz „Relatywizacja klas małych złożoności i ich teorii” Klausa Aehliga, Stephena Cooka i Phuonga Nguyena, CSL 2007.

Kaveh

@Marcos: Wierzę, że odpowiedź jest po prostu wewnętrznym stanem maszyny i nie jest zapisana na taśmie wyroczni.

Joe Fitzsimons,

Jakie jest odniesienie do tej definicji kosmicznych maszyn wyroczni?

miforbes,

10

Myślę, że jednym zaskakującym faktem jest to, że w tym modelu twierdzenie Savitcha nie „oczywiście” relatywizuje. Oznacza to, że można zauważyć, że i w tym modelu, a obecnie nie wiedzieć, że $PSPACE^P=EXPTIME$ $NPSPACE^P=NEXPTIME$ (i wydaje się, że twierdzenie Savitcha w tym kontekście nie daje). Byłbym zainteresowany, czy można to zepchnąć do „niewiarygodnego” braku relatywizacji. $EXPTIME=NEXPTIME$

Można również zaobserwować, że w tym modelu. $NL^{NL}=NL^L=NP$

Myślę jednak, że ten model warto przynajmniej przemyśleć, jeśli chodzi o kwestie relatywizacji w twierdzeniu o hierarchii przestrzeni. Ponadto, w pewnym sensie, chcę aby poli wielkości zapytań do . $L^A$ $A$

Miforbes
źródło

1

Jedno zapomniałem: jako NL = coNL powinniśmy chcieć NL ^ NL = NL, ale oczywiście jeśli NL ^ NL = NP w tym modelu nie możemy użyć NL = coNL do zwinięcia „NL-hierachy”. W innym pojęciu wyroczni ograniczonych przestrzenią hierarchia rzeczywiście się załamuje (patrz odniesienia Immerman's NL = coNL).

miforbes,

Czy masz referencje? By się było spodziewać

. Rzeczywiście, niech

jest językiem rekurencyjnie wyliczalnych,

baza TM, które rozpoznają

i

ma Tm odczytać wejście i szereg

„1”, a następnie symuluje

na tym wejściu w

krokach. Następnie bez użycia miejsca mógłbym skopiować dane wejściowe na taśmie wyroczni, odgadnąć potrzebną liczbę 1 i zapytać

.

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'$

Arthur MILCHIOR

9

To może nie odpowiedzieć na twoje pytanie (które szczerze mówiąc nie do końca rozumiem), ale myślę, że jest w tym samym duchu. Wiadomo, że istnieje różnica w redukowalności między logspace TM z jedną taśmą Oracle i jedną z dostępem do wielu taśm Oracle. Ponadto następujące pojęcie logspaceness ma ładne właściwości: TM może używać tylko logarytmicznej ilości miejsca na swojej taśmie roboczej, ale może wykorzystywać wielomianową ilość miejsca na swoich taśmach Oracle.

Odniesienie: http://groups.csail.mit.edu/tds/papers/Lynch/tcs78.pdf

Aaron Sterling
źródło

3

NSPACE (0) P = RE, które, jak sądzę, jest nieco absurdalne.

Rzeczywiście, niech L będzie językiem rekurencyjnie wyliczalnym, M TM, która rozpoznaje L i M'TM, które odczytują dane wejściowe i liczbę n „1”, a następnie symulują M dla tego wejścia na n krokach. Następnie bez użycia miejsca mógłbym skopiować dane wejściowe na taśmie wyroczni, odgadnąć potrzebną liczbę 1 i zapytać M ′.

Wtedy M 'zaakceptuje iff M accept i będzie miał wystarczająco duży sygnał wejściowy, aby być wielomianem.

Arthur MILCHIOR
źródło

kosmiczne bazy TM i wyrocznie

Odpowiedzi: