Kompromis czasoprzestrzenny i najlepszy algorytm

Rozważmy język taki jak: $L$

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

i tak

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

Innymi słowy, najszybsza maszyna oblicza w czasie a najbardziej wydajna pod względem przestrzeni maszyna oblicza , używając przestrzeni . $M$ $L$ $O(f(n))$ $M'$ $L$ $O(g(n))$

Co można powiedzieć o wydajności przestrzennej M lub wydajności czasowej M? Lub bardziej precyzyjnie, jeśli jest zbiorem wszystkich maszyn, które obliczają w to co można powiedzieć o większości przestrzeni wydajnej maszyny w ? Co o tym samym dla oczywistej wersji Space: . $\mathbb{M}_T$ $L$ $O(f(n))$ $\mathbb{M}_T$ $\mathbb{M}_S$

Można i jest stosowany do określenia pewnych kompromisów dobre przestrzenno-czasową? W jakich warunkach lub bardziej ogólnie dla niektórych kompromisów czasoprzestrzennych w jakich warunkach jest $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
źródło

Czy pytasz o dowolny L, czy jesteś zainteresowany wynikami tego rodzaju, które mogą istnieć w przypadku konkretnych problemów?

Suresh Venkat

Naprawdę interesuje mnie jedno i drugie. Moją pierwotną motywacją były głównie problemy z osiągalnością (ukierunkowana i nieukierowana łączność st). Interesujące byłoby jednak wiedzieć, czy dostępne są jakieś ogólne granice lub techniki.

Artem Kaznatcheev

Tak, każdą językową rozstrzygalne

. Ten język udostępnia funkcje

dzięki czemu

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))]$ (Czy to prawda, czy też istnieją języki przyspieszające, które ją naruszają?)

Derrick Stolee

W szczególności istnieją przykłady w zakresie wyszukiwania problemów, które dopuszczają (zapytanie, spację) formy (log n, poli (n)) lub (sublinearny, liniowy) lub ich dowolną interpolację

Suresh Venkat

Związane z? Kompromis czasoprzestrzenny w dolnych granicach

Tsuyoshi Ito

Odpowiedzi:

Prototypowe f i g prawdopodobnie byłyby wielomianem i przestrzenią polilogu. Interesującym problemem jest tutaj łączność (w grafach ukierunkowanych), którą można rozwiązać w czasie wielomianowym (przy użyciu przestrzeni liniowej) lub w przestrzeni polilogu (przy użyciu czasu wielomianowego). Znanym otwartym problemem jest to, czy można go rozwiązać w TIME-SPACE (poly, polylog), klasie znanej jako SC .

To znaczy, twoje pytanie jest dobrze znanym otwartym problemem. Nie sądzę, aby znane było tu coś nietrywialnego.

Noam
źródło

Dziękuję za odpowiedź. Podejrzewałem, że będzie to otwarty problem, ale mam nadzieję, że pewne konkretne wyniki będą już znane. Niefortunne :(.

Artem Kaznatcheev

-4

to pytanie pojawiło się na „podobnych pytaniach”, kiedy właśnie opublikowałem to drugie pytanie /cstheory/9677/deterministic-time-space-separation-via-space-compression .

tam cytuję wynik Hopcroft, Paul, Valiants 1977 (najwyraźniej najlepiej znany według rj liptona na jego blogu), który wydaje się dotyczyć twojego pytania, tj. $\mathsf{DTIME}(t(n)) \subseteq \mathsf{DSPACE}(t(n)/log(n))$

vzn
źródło

I don't see how this applies to time-space trade-offs...

Artem Kaznatcheev

the concept of "time space tradeoff" seems not to be exactly defined. my answer can be understood as follows: a program that is in DTIME(t(n)) is "naturally" in DSPACE(t(n)). the HPV1977 results then allow one to construct a TM, at the expense of some increase in states (and tapes maybe?) such that it takes DSPACE(t(n)/log(n)) space instead. therefore a "tradeoff"

vzn

There is a standard understanding of trade-offs in CS which is not at all what you describe (what you describe is not a trade-off at all, but just a standard relationship between DTIME and DSPACE). Further, I explicitly explain what I want in time-space trade-off in my question, please read questions carefully before trying to answer them.

Artem Kaznatcheev

if your definition of time-space tradeoffs above in your question is standard as you say, is it defined in any literature?

vzn

looking over your definition it looks intuitively plausible that such f(n),g(n) exist for all decidable languages but wouldnt one run into problems even proving such f(n),g(n) necessarily exist due to the blum speedup theorem....?

vzn