Wyraźny rozdział między konstruowaniem w czasie a konstruowaniem w przestrzeni?

Pokaż funkcję którą można konstruować w przestrzeni, ale nie można jej konstruować w czasie. $f(n)$

Czy ten problem jest związany z możliwym rozdzieleniem klas złożoności DTIME (f (n)) i SPACJA (f (n))?

cc.complexity-theory space-bounded separation Tian Liu
źródło

en.wikipedia.org/wiki/Constructible_function O ile mi wiadomo, to pytanie nie ma związku z TIME (f (n)) vs SPACE (f (n)), ale zauważ, że te dwie klasy są różne. Poszukaj artykułów „Na czas kontra przestrzeń”, „Na czas kontra przestrzeń II”, „Na czas kontra przestrzeń III”

Ryan Williams

Szybka obserwacja: Myślę, że problem jest równoznaczny z pytaniem, czy DTIME (f (n)) ALLTALLY i SPACJA (f (n)) ALLTALLY mogą być różne dla niektórych funkcji f (n), które można konstruować w przestrzeni, gdzie TALLY jest klasa języków, które są podzbiorami 1 ^ *.

Tsuyoshi Ito

Ups, mogą nie być równoważne. Oto dowód jednego kierunku. Jeśli istnieje język L = {1 ^ n | n∈S} ∈ TALLY∩ (SPACJA (f (n)) ∖ DTIME (f (n))) dla niektórych funkcji f (n), które można konstruować w przestrzeni, a następnie zarówno f (n) i f (n) + χ_S (n ) (gdzie χ_S (n) jest funkcją charakterystyczną S) są konstruowalne w przestrzeni, ale nie oba są konstruowalne w czasie, a zatem co najmniej jedna z nich jest funkcją konstruowaną w przestrzeni, ale nie konstruowaną w czasie.

Tsuyoshi Ito,

Dzięki Ryanowi w twoim komentarzu wiem, że CZAS (f (n)) jest zawarty w PRZESTRZENI (f (n) / log f (n)) autorstwa Hopcroft i in., A ten drugi jest odpowiednio zawarty w PRZESTRZENI (f (n )) według twierdzenia o hierarchii przestrzeni.

Tian Liu,

Dzięki Tsuyoshi bardzo sprytne pomysły, jeśli zarówno f (n), jak i f (n) + χ_S (n) są konstruowalne w czasie, wówczas możemy zdecydować, czy n∈S przypada co najwyżej f (n) +1, a zatem L ALLTALLY ∩ DTIME (f (n)), sprzeczność. ale czy twoje konstrukcje można nazwać „eksplodować”? który nie jest konstruowalny w czasie, f (n) lub f (n) + χ_S (n)? przez „wyraźne”, jeśli mam na myśli to, że możemy zdecydować o wartości f (n) dla wszystkich n, wówczas twoja konstrukcja jest jasna.

Tian Liu,

Odpowiedzi:

Funkcja jest konstruowalna w czasie, jeśli istnieje maszyna Turinga która na wejściu oblicza funkcję w czasie . $T \colon \mathbb{N} \to \mathbb{N}$ $M$ $1^n$ $x \mapsto T(|x|)$ $O(T(n))$

Funkcja jest konstruowalna w przestrzeni, jeśli istnieje maszyna Turinga która na wejściu oblicza funkcję w przestrzeni . $S \colon \mathbb{N} \to \mathbb{N}$ $M$ $1^n$ $x \mapsto S(|x|)$ $O(S(n))$

Niektóre teksty wymagają, aby funkcje konstruowane w czasie / przestrzeni nie zmniejszały się. Niektóre teksty wymagają, aby funkcje konstruowane w czasie spełniały , a funkcje konstruowane w przestrzeni spełniały . Niektóre teksty nie wykorzystują zapisu w definicji. $T(n)\ge n$ $S(n)\ge \log n$ $O(\cdot)$

W każdym razie łatwo jest wykazać, że każda „zwykła” funkcja spełniająca oraz jest konstruowalna w przestrzeni, ale nie jest konstruowana w czasie. $f$ $f(n)\ge \log n$ $f(n) = o(n)$

Problem konstrukcyjności nie jest bezpośrednio związany z możliwym rozdzieleniem klas złożoności DTIME (f (n)) i SPACJA (f (n)). Jednak twierdzenia dotyczące hierarchii czasu i przestrzeni uwzględniają konstruktywność. Na przykład:

Twierdzenie o hierarchii czasu Jeśli , są funkcjami konstruowanymi w czasie spełniającymi , to jest właściwym podzbiorem . $f$ $g$ $f(n)\log f(n) = o(g(n))$ $\mathbf{DTIME}(f(n))$ $\mathbf{DTIME}(g(n))$

Zobacz Arora & Baraka książkę lub zPapadimitriou aby uzyskać więcej informacji. (Ten ostatni używa terminu „właściwa funkcja złożoności” w odniesieniu do takiej, która jest możliwa do zbudowania zarówno w czasie, jak i przestrzeni).

MS Dousti
źródło

Dzięki. Wolę definicję, że funkcję można konstruować w czasie / przestrzeni, jeśli istnieje maszyna Turinga, która działa dokładnie tak, jak kroki / kwadraty taśmy. Oczywiście, według twierdzeń o liniowym przyspieszeniu czasu / przestrzeni, jest to równoważne z definicjami / podręcznika.

Tian Liu,

Sadeq, twoje definicje „konstruowalnego w czasie” i „konstruowalnego w przestrzeni” są identyczne dla każdego słowa. Czy mówisz, że to tylko dwie różne nazwy dla dokładnie tego samego pojęcia? Jeśli nie, być może powinieneś naprawić swoje definicje.

Yitz

To tylko literówka.

Tsuyoshi Ito,

Przepraszam, Yitz. Naprawiłem literówkę.

MS Dousti,

można konstruować w przestrzeni, ale nie w czasie. Powodem jest to, że można odwzorować na reprezentację binarną w przestrzeni ale nie w czasie . $f(n)=\log n$ $1^n$ $O(\log n)$ $O(\log n)$

Mohammad Al-Turkistany
źródło

Dzięki komentarzowi i odpowiedzi. Ale czy możesz pokazać funkcję f (n), która jest co najmniej liniowa, to znaczy f (n)> = n, dla separacji? Wydaje się, że funkcja, którą można konstruować w czasie, nie może być mniejsza niż n z oczywistego powodu: musi odczytać wszystkie bity wejściowe, w przeciwnym razie argument przeciwnika może pokazać, że funkcja nie jest poprawnie obliczona.

Tian Liu,

@Tian,

jest funkcją konstruowaną w przestrzeni, ale nie konstruowaną w czasie.

f (n) = n

$f(n)= n$

Mohammad Al-Turkistany

Jeszcze raz dziękuję, ale czy zakładasz, że głowica czytająca na taśmie wejściowej początkowo znajduje się po lewej stronie do pierwszego bitu wejściowego? w takim przypadku, aby wykryć ostatni bit danych wejściowych, głowa musi przejść w prawo n + 1 razy, aż napotka pierwszy pusty wpis po wejściu. Zatem

można konstruować w czasie. Więc proszę podać „nietrywialny” rozdział funkcją f (n)> = n + 1?

f (n) = n + 1

$f(n)=n+1$

Tian Liu,

Jeśli wszystkie funkcje kosmiczne konstruowalne są czasu konstruowalne, a . Aby to udowodnić (i podać przykład nietrywialnej funkcji konstruowanej w przestrzeni, ale przypuszczalnie nie konstruowanej w czasie), weźmy dowolną (prawdopodobnie ) problem $EXP-TIME=EXP-SPACE$ $EXP-SPACE-COMPLETE$ , . Następnie istnieje , st można rozwiązać za pomocą DTM wprzestrzeni . Teraz zdefiniuj funkcję $L\in EXP-SPACE$ $L\subseteq\{0,1\}^*$ $k\in\mathbb{N}$ $L$ $M$ $2^{n^k}$

fa (n) = {\begin{cases} 8 n + 2) & gdyby (pierwszy ⌊ \sqrt[k]{⌊ \log n ⌋ + 1} ⌋ kawałki b ja n (n)) \in L. \\ 8 n + 1 & jeszcze \end{cases}

$f(n)=\left\{\begin{array}{ll} 8n+2 & \mbox{if }\left(\mbox{first } \lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\mbox{ bits of } bin(n)\right)\in L\\ 8n+1 & \mbox{else} \end{array} \right.$

$2n$ $f$ $f$ $L$

Ta odpowiedź wykorzystuje ten sam pomysł.

David G.
źródło