Tradeoff ruang-waktu dan algoritma terbaik

Pertimbangkan beberapa bahasa sedemikian rupa sehingga: $L$

$L \in DTIME(O(f(n))) \cap DSPACE(O(g(n)))$

dan jadi itu

$L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n)))$

Dengan kata lain, mesin tercepat menghitung dalam waktu dan mesin paling efisien ruang menghitung saat menggunakan ruang . $M$ $L$ $O(f(n))$ $M'$ $L$ $O(g(n))$

Apa yang dapat dikatakan tentang efisiensi ruang M atau efisiensi waktu M '? Atau lebih tepatnya, jika adalah himpunan semua mesin yang menghitung dalam lalu apa yang bisa kita katakan tentang mesin paling hemat ruang di ? Bagaimana dengan hal yang sama untuk versi luar angkasa yang jelas: . $\mathbb{M}_T$ $L$ $O(f(n))$ $\mathbb{M}_T$ $\mathbb{M}_S$

Atau, dapatkah dan digunakan untuk mendefinisikan beberapa pertukaran ruang-waktu yang baik? Dalam kondisi apa atau lebih umum untuk beberapa pertukaran ruang-waktu dalam kondisi apa . $f(n)$ $g(n)$ $TS \in o(f(n)g(n))$ $h(T,S)$ $h(T,S) \in h(o(f(n)),o(g(n)))$

cc.complexity-theory ds.algorithms open-problem space-time-tradeoff Artem Kaznatcheev
sumber

Apakah Anda bertanya tentang L yang sewenang-wenang, atau Anda tertarik pada hasil seperti ini yang mungkin ada untuk masalah khusus?

Suresh Venkat

Saya tertarik pada keduanya, sungguh. Motivasi asli saya sebagian besar dari masalah keterjangkauan (konektivitas langsung dan tidak langsung). Namun, akan menarik untuk mengetahui apakah ada batasan umum atau teknik yang tersedia.

Artem Kaznatcheev

Jadi, mengambil bahasa decidable

. Bahasa ini memberikan fungsi

sehingga

dan

L

$L$

f_{L}, g_{L}

$f_L, g_L$

L \in TIME [f_{L} (n)] \cap SPACE [g_{L} (n)]

$L \in \text{TIME}[f_L(n)] \cap \text{SPACE}[g_L(n)]$

L \notin TIME [o (f_{L} (n))] \cup SPACE [o (g_{L} (n))]

$L \not\in \text{TIME}[o(f_L(n))] \cup \text{SPACE}[o(g_L(n))]$ . (Apakah ini benar, atau adakah bahasa "percepatan" yang melanggarnya?)

Derrick Stolee

Secara khusus, ada contoh dalam rentang pencarian masalah yang menerima (Query, Space) dari formulir (log n, poly (n)), atau (sublinear, linier), atau interpolasi daripadanya

Suresh Venkat

Terkait? Batas bawah tradeoff ruang-waktu

Tsuyoshi Ito

Jawaban:

Prototip f dan g di sini mungkin akan menjadi ruang waktu-poli dan polylog. Masalah yang menarik di sini adalah konektivitas (dalam grafik terarah) yang dapat diselesaikan dalam waktu polinomial (menggunakan ruang linear) atau dalam ruang polylog (menggunakan waktu super-polinomial). Ini adalah masalah terbuka yang terkenal apakah itu dapat diselesaikan dalam TIME-SPACE (poli, polylog), kelas yang dikenal sebagai SC .

Yaitu pertanyaan Anda adalah masalah terbuka yang terkenal. Saya tidak berpikir bahwa sesuatu yang non-sepele dikenal di sini.

Noam
sumber

Terima kasih atas jawabannya. Saya mencurigai itu akan menjadi masalah terbuka, tetapi berharap bahwa beberapa hasil spesifik sudah tahu. Sayangnya :(.

Artem Kaznatcheev

-4

pertanyaan ini muncul pada "pertanyaan serupa" ketika saya baru saja memposting pertanyaan lain ini /cstheory/9677/deterministic-time-space-separation-via-space-compression .

di sana saya mengutip hasil hopcroft, paul, valiants 1977 (tampaknya paling terkenal menurut rj lipton di blog-nya) yang tampaknya berlaku untuk pertanyaan Anda yaitu $\mathsf{DTIME}(t(n)) \subseteq \mathsf{DSPACE}(t(n)/log(n))$

vzn
sumber

Saya tidak melihat bagaimana ini berlaku untuk trade-off ruang-waktu ...

Artem Kaznatcheev

konsep "tradeoff ruang waktu" tampaknya tidak didefinisikan secara tepat. jawaban saya dapat dipahami sebagai berikut: program yang ada di DTIME (t (n)) "alami" di DSPACE (t (n)). hasil HPV1977 kemudian memungkinkan seseorang untuk membangun TM, dengan mengorbankan beberapa peningkatan status (dan kaset mungkin?) sehingga dibutuhkan ruang DSPACE (t (n) / log (n)) sebagai gantinya. oleh karena itu "tradeoff"

vzn

Ada pemahaman standar tentang trade-off di CS yang sama sekali tidak seperti yang Anda gambarkan (apa yang Anda gambarkan bukanlah trade-off sama sekali, tetapi hanya hubungan standar antara DTIME dan DSPACE). Lebih jauh, saya secara eksplisit menjelaskan apa yang saya inginkan dalam pertukaran waktu-waktu dalam pertanyaan saya, harap baca pertanyaan dengan seksama sebelum mencoba menjawabnya.

Artem Kaznatcheev

jika definisi Anda tentang pertukaran ruang-waktu di atas dalam pertanyaan Anda adalah standar seperti yang Anda katakan, apakah definisi itu didefinisikan dalam literatur apa pun?

vzn

melihat definisi Anda secara intuitif tampak masuk akal bahwa f (n), g (n) seperti itu ada untuk semua bahasa yang dapat didekati, tetapi tidakkah orang akan mengalami masalah bahkan untuk membuktikan f (n), g (n) itu pasti ada karena teorema speedum blum ....?

vzn