Apakah DSPACE (n) = DSPACE (1.5n)?

Dari teorema ruang-hierarki diketahui bahwa jika $f$ -ruang-dibangun maka DSPACE ( $2f(n)$ ) tidak sama dengan DSPACE ( $f(n))$ .

Di sini, oleh DSPACE ( $f(n))$ saya maksud adalah kelas semua masalah yang dapat diselesaikan dalam ruang $f(n)$ oleh mesin Turing dengan beberapa alfabet tetap. Hal ini memungkinkan untuk mempertimbangkan teorema Space-hierarki dengan akurasi seperti itu.

Argumen standar memberikan konstanta multiplikasi : kita membutuhkan ruang untuk membangun perhitungan beberapa mesin Turing dengan yang universal. Kita juga perlu untuk menyelesaikan masalah dengan penghentian. $2$ $f(n)$ $f(n)$

Pertanyaan: Apakah DSPACE ( ) sama dengan DSPACE ( )? $f(n)$ $\frac{3}{2}f(n)$

cc.complexity-theory complexity-classes Alexey Milovanov
sumber

alasan Anda tertarik pada ? Apakah sama-sama menarik?

\frac{3}{2}

$\frac32$

1 + Ω (1)

$1+\Omega(1)$

Thomas

Mengapa Anda berpikir bahwa teorema ruang-hierarki memberikan ? Saya kira Anda berpendapat bahwa kami membutuhkan ruang untuk simulasi dan ruang untuk menghitung jumlah langkah untuk menghindari loop tak terbatas. Tetapi dalam kedua kasus tersebut, kita perlu menandai lokasi pada pita (dapat dilakukan karena adalah ruang-konstruktif) dan bagaimana Anda akan melakukan penandaan? Argumen Anda OK jika Anda menganggap bahwa mesin tidak diperbolehkan untuk menulis *, tetapi sebaliknya beberapa komplikasi lebih lanjut diperlukan.

2 f (n)

$2f(n)$

f (n)

$f(n)$

\log_{| Σ |} | Σ |^{f (n)}

$\log_{|\Sigma|} |\Sigma|^{f(n)}$

f (n)

$f(n)$

f

$f$

domotorp

@ Thomas Sebenarnya saya ingin

1 + o (1)

$1 + o(1)$

Alexey Milovanov

Dapat dibuktikan bahwa DSPACE DSPACE jika tumbuh setidaknya secara linear dengan menggunakan varian sederhana dari argumen padding standar. Untuk bahasa , misalkan . $(f(\frac 32 n))\ne$ $(f(n))$ $f$ $L$ $L'=\{x0^{|x|/2}\mid x\in L\}$

Klaim. DSPACE jika dan hanya jika DSPACE jika . $L\in$ $(f(n))$ $L'\in$ $(f(\frac 23n))$ $f(n)\ge \frac 32n$

(Jawaban pertama saya memiliki beberapa pernyataan yang salah, terima kasih kepada Emil untuk mengetahui ini.)

Pertama-tama saya akan menunjukkan cara menggunakan klaim untuk membuktikan hierarki. Karena tumbuh setidaknya secara linear, kami memiliki DSPACE DSPACE . Ambil bahasa DSPACE $f$ $(2f(n))\subset$ $(f(2n))$ $L\in$ $(f(2n))\setminus$ DSPACE . Menggunakan klaim, DSPACE DSPACE , di mana kesetaraan terakhir adalah dengan asumsi tidak langsung. Tetapi kemudian DSPACE DSPACE , di mana kesetaraan terakhir lagi dengan asumsi tidak langsung, memberikan kontradiksi. $(f(n))$ $L'\in$ $(f(\frac 43 n))=$ $(f(n))$ $L\in$ $(f(\frac 32 n))=$ $(f(n))$

Bukti klaim. Jika DSPACE $L'\in$ $(f(\frac 23 n))$ , maka untuk membuktikan DSPACE , kita hanya perlu menulis 0's di akhir input dan mensimulasikan mesin yang menerima . Karena , ini tidak akan menambah ruang yang kita gunakan. (Faktanya, mengetahui berapa 0 untuk menulis tidak jelas sama sekali jika kecil dan kita tidak dapat meningkatkan ukuran alfabet - sebagai gantinya, kita dapat menggunakan kaset lain dan menulis bahwa segala sesuatu yang akan datang setelah akhir .) $L\in$ $(f(n))$ $|x|/2$ $x$ $L'$ $f(n)\ge \frac 32 n$ $f$ $x$

Arah lainnya hanya sesederhana ini dengan mengganti 0 dengan *, jika kita diizinkan menulis *. (Lihat masalah dengan ini di komentar saya untuk pertanyaan.) Jika kita tidak diizinkan untuk menulis bintang, maka kita sedikit mengubah definisi sebagai . Sekarang, alih-alih menulis bintang, kami menyimpan input asli $L'$ $L'=\{x10^{|x|/2}\mid x\in L\}$ $x10^{|x|/2}$ dan bekerja dengan itu. Tetapi setiap kali kita mencapai angka 1, kita ke kanan sampai kita menekan angka 1 yang lain untuk memeriksa apakah itu kata akhir 1 atau tidak. Jika kami telah menemukan 1 lainnya, kami hanya kembali ke 1. kami. Jika belum, kami masih kembali, tetapi kami akan tahu bahwa itu harus diperlakukan sebagai bintang - jika kami ingin menulis di atasnya, maka kami juga menulis 10 setelahnya untuk memiliki penanda akhir kata saat ini. (Bahkan, ada juga tangkapan kecil di bagian ini jika kecil - bagaimana kita dapat memeriksa apakah inputnya dalam bentuk ? Tanpa merusak input, saya hanya dapat menyelesaikan ini dengan menggunakan beberapa kepala untuk kecil .) $f$ $x10^{|x|/2}$ $f$

domotorp
sumber

Saya tidak mengerti argumen sama sekali. Apa pun cara saya melihatnya, konstruksi padding hanya menunjukkan bahwa jika , maka , yang cukup berbeda dari klaim (perhatikan lokasi ). Demikian juga, arah yang berlawanan sama sekali tidak jelas seperti yang dinyatakan, yang hanya jelas bagi saya adalah bahwa jika , maka . Bahkan jika saya mengambil klaim pada nilai nominal, bukti hasil utama salah: hanya memberikan .

L \in D S P A C E (f (n))

$L\in\mathrm{DSPACE}(f(n))$

L^{'} \in D S P A C E (f (\frac{2}{3} n))

$L'\in\mathrm{DSPACE}(f(\frac23n))$

\frac{2}{3}

$\frac23$

L^{'} \in D S P A C E (f (\frac{2}{3} n))

$L'\in\mathrm{DSPACE}(f(\frac23n))$

L \in D S P A C E (f (n) + \frac{n}{2})

$L\in\mathrm{DSPACE}(f(n)+\frac n2)$

L \in D S P A C E (2 f (n))

$L\in\mathrm{DSPACE}(2f(n))$

L^{'} \in D S P A C E (\frac{4}{3} f (n) + \frac{n}{3}))

$L'\in\mathrm{DSPACE}(\frac43f(n)+\frac n3))$

Emil Jeřábek

@Emil Anda benar. Saya mencoba memperbaikinya, apakah terlihat lebih baik?

domotorp

L^{'} \in D S P A C E (f (\frac{2}{3} n)) ⟹ L \in D S P A C E (f (n))

$L'\in\mathrm{DSPACE}(f(\frac23n))\implies L\in\mathrm{DSPACE}(f(n))$

O (\log n)

$O(\log n)$

f

$f$

D S P A C E (f (n)) ⊊ D S P A C E ((1 + ϵ) f (n))

$\mathrm{DSPACE}(f(n))\subsetneq\mathrm{DSPACE}((1+\epsilon)f(n))$ untuk konstanta dengan mengulangi argumen.

ϵ > 0

$\epsilon>0$

Emil Jeřábek

@Emil Saya tidak berpikir kaset input hanya baca - AFAIK yang hanya diasumsikan jika .

f (n) < n

$f(n)<n$

domotorp

Apakah DSPACE (n) = DSPACE (1.5n)?

Jawaban: