TM dan oracle yang dibatasi ruang

20

Secara umum, query-tape untuk oracle diperhitungkan dalam kompleksitas ruang TM. Namun, tampaknya masuk akal untuk memungkinkan rekaman-saja oracle-tape (seperti yang digunakan dalam pengurangan ruang-L).

Apakah konstruksi seperti itu bermanfaat? Apakah itu menghasilkan hasil yang sangat tidak masuk akal?

cc.complexity-theory space-bounded oracles Jeremy Hurwitz
sumber

Jika Anda seorang TM dengan rekaman Oracle hanya-menulis, bagaimana Anda membaca jawabannya? Anda bisa melupakan oracle saja.

Marcos Villagra

1

Ada masalah rumit dalam memutuskan apa definisi yang tepat dari akses oracle untuk mesin yang terikat ruang. Lihat "Merelatifikasi Kelas Kompleksitas Kecil dan Teori-teorinya" oleh Klaus Aehlig, Stephen Cook, dan Phuong Nguyen, CSL 2007.

Kaveh

@ Marscos: Saya percaya jawabannya hanyalah keadaan internal mesin yang dihasilkan, dan tidak ditulis ke pita oracle.

Joe Fitzsimons

Apa referensi untuk definisi mesin oracle yang dibatasi ruang ini?

miforbes

10

Saya pikir satu fakta yang mengejutkan adalah bahwa dalam model ini teorema Savitch tidak "jelas" merelatifkan. Artinya, orang dapat melihat bahwa dan dalam model ini, dan kami saat ini tidak tahu bahwa $PSPACE^P=EXPTIME$ $NPSPACE^P=NEXPTIME$ $EXPTIME=NEXPTIME$ (dan teorema Savitch dalam konteks ini tampaknya tidak memberikannya). Saya akan tertarik pada apakah ini dapat didorong untuk "terbukti" non-relativizing.

Kita juga dapat mengamati bahwa dalam model ini. $NL^{NL}=NL^L=NP$

Namun, saya berpikir bahwa model ini setidaknya layak untuk dipikirkan, sehubungan dengan masalah relativisasi dalam teorema hierarki ruang. Juga, dalam arti, saya ingin membuat query poli berukuran ke . $L^A$ $A$

miforbes
sumber

1

Satu hal yang saya lupa: sebagai NL = coNL kita harus menginginkan NL ^ NL = NL, tetapi jelas jika NL ^ NL = NP dalam model ini kita tidak dapat menggunakan NL = coNL untuk menutup "NL-hierachy". Dalam gagasan berbeda tentang oracle yang dibatasi oleh ruang, hierarki memang runtuh (lihat makalah Immerman's NL = coNL untuk referensi).

miforbes

Apakah Anda punya referensi? Saya akan diharapkan

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

$\rm{NSPACE(0)^P=RE}$ . Memang, biarkan

menjadi bahasa yang berulang secara berulang,

a TM yang mengenali

dan

TM yang membaca input dan angka

dari "1" dan kemudian mensimulasikan

untuk input ini pada

langkah. Kemudian tanpa menggunakan ruang apa pun saya bisa menyalin input pada rekaman oracle, tebak jumlah 1 yang dibutuhkan dan permintaan

.

L

$L$

M

$M$

L

$L$

M^{'}

$M'$

n

$n$

M

$M$

n

$n$

M^{'}

$M'$

Arthur MILCHIOR

9

Ini mungkin tidak menjawab pertanyaan Anda (yang sejujurnya saya tidak sepenuhnya mengerti), tetapi saya pikir itu dalam semangat yang sama. Diketahui bahwa ada perbedaan dalam reducibilitas antara logspace TM dengan satu pita oracle, dan satu dengan akses ke beberapa kaset oracle. Juga, gagasan logspaceness berikut memiliki sifat yang bagus: TM hanya dapat menggunakan jumlah log-ruang pada pita kerjanya, tetapi ia dapat menggunakan jumlah ruang polinomial pada kaset oracle-nya.

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

Aaron Sterling
sumber

3

NSPACE (0) P = RE yang kurasa sedikit absurd.

Memang, biarkan L menjadi bahasa yang berulang secara berulang, M a TM yang mengenali L dan M ′ TM yang membaca input dan angka n dari "1" dan kemudian mensimulasikan M untuk input ini pada n langkah. Kemudian tanpa menggunakan ruang apa pun saya bisa menyalin input pada pita oracle, tebak jumlah 1 yang dibutuhkan dan permintaan M ′.

Kemudian, M 'akan menerima jika M menerima dan memiliki input yang cukup besar untuk jumlahnya banyak.

Arthur MILCHIOR
sumber

TM dan oracle yang dibatasi ruang

Jawaban: