Równoważne definicje konstruowania czasu

Mówimy, że funkcja jest konstruowalna w czasie , jeśli istnieje deterministyczna wielopasmowa maszyna Turinga która na wszystkich wejściach długości wykonuje co najwyżej kroki i dla każdego istnieje pewien wkład długość na której wykonuje dokładnie kroki. $f:\mathbb{N}\rightarrow\mathbb{N}$ $M$ $n$ $f(n)$ $n$ $n$ $M$ $f(n)$

Mówimy, że funkcja jest w pełni konstruowalna w czasie , jeśli istnieje deterministyczna wielopasmowa maszyna Turinga która na wszystkich wejściach długości wykonuje dokładnie kroków. $f:\mathbb{N}\rightarrow\mathbb{N}$ $M$ $n$ $f(n)$

P1: Czy istnieje funkcja, którą można konstruować w czasie i nie można w pełni konstruować w czasie?

Odpowiedź brzmi: tak (patrz tę odpowiedź ), jeśli . Czy warunek „tak” można wzmocnić do ? Czy można udowodnić „tak”? $EXP-TIME \neq NEXP-TIME$ $P\neq NP$

P2: Czy klasa funkcji (w pełni) składających się na czas zmienia się, jeśli w definicji dopuszczamy tylko 2-taśmowe maszyny Turinga?

P3: Jakie są „możliwe do udowodnienia” powody, by sądzić, że wszystkie ładne funkcje można w pełni konstruować w czasie?

Artykuł
Kojiro Kobayashi: O sprawdzaniu możliwości konstruowania funkcji w czasie. Teoria Comput. Sci. 35: 215-225 (1985)
częściowo odpowiada na pytanie 3. Częściowe podsumowanie i uaktualnienie znajduje się w tej odpowiedzi . Biorę Q3 jako odpowiedź.

Historycznie używano pojęcia funkcji policzalnej w czasie rzeczywistym zamiast (w pełni) konstruowalnej w czasie. Zobacz to pytanie, aby uzyskać więcej.

cc.complexity-theory time-complexity terminology

— David G.
źródło

Ciekawy - czy możesz wskazać mi odniesienie do tych definicji? Nie znam funkcji konstruowalnych i nie mogę znaleźć tych definicji online (nie jest dla mnie oczywiste, czy są one równoważne np. Z wikipediami ).

— usul

@usul Referencje: JE Hopcroft, JD Ullman. Wprowadzenie do teorii automatów, języków i obliczeń. Addison-Wesley Series in Computer Science, 1979 Tę samą definicję można znaleźć tutaj: cse.ohio-state.edu/~gurari/theory-bk/theory-bk-fivese2.html

— David G

W ciągu ostatnich kilku dni dużo myślałem o (w pełni) konstruowalnych w czasie funkcjach i przedstawię to, czego się dowiedziałem, odpowiadając na pytania 1 i 3. Pytanie 2 wydaje się zbyt trudne.

P3:

Kobayashi w swoim artykule (odniesienie znajduje się w pytaniu) udowodnił, że funkcja , dla której istnieje st , jest w pełni konstruowalna w czasie, jeśli jest obliczalny w czasie . (zauważ, że nie ma znaczenia, czy dane wejściowe czy wyjściowe są jednostkowe / binarne, ponieważ możemy transformować te dwie reprezentacje w czasie liniowym). Dzięki temu następujące funkcje są w pełni konstruowane w czasie: , $f:\mathbb{N}\rightarrow\mathbb{N}$ $\epsilon>0$ $f(n)\geq (1+\epsilon)n$ $O(f(n))$ $2^n$ ,, , wszystkie wielomiany ponad st ... Kobayashi również wykazał pełną konstruowalność czasową dla niektórych funkcji, które rosną wolniej niż , jak dla ... $2^{2^n}$ $n!$ $n\lfloor \log n \rfloor$ $p$ $\mathbb{N}$ $p(n)\geq (1+\epsilon)n$ $(1+\epsilon)n$ $n+\lfloor\lfloor\log n\rfloor^q\rfloor$ $q\in\mathbb{Q}^+$

Kontynuując przykłady funkcji w pełni konstruowalnych w czasie, można udowodnić, że jeśli i są w pełni konstruowalne w czasie, to , , i są również w pełni konstruowalny w czasie (później wynika bezpośrednio z Twierdzenia 3.1 w Kobayashi). To całkowicie mnie przekonało, że wiele fajnych funkcji jest rzeczywiście w pełni konstruowanych w czasie. $f_1$ $f_2$ $f_1+f_2$ $f_1f_2$ $f_1^{f_2}$ $f_1\circ f_2$

Zaskakujące jest to, że Kobayashi nie widział sposobu, aby udowodnić pełną konstruowalność w czasie (ładnej) funkcji (i ja też nie). $\lfloor n\log n\rfloor$

Skomentujmy również definicję z artykułu z Wikipedii : Funkcja jest konstruowalna w czasie, jeśli istnieje maszyna Turinga która, biorąc pod uwagę ciąg , wyprowadza w czasie . $f$ $M$ $1^n$ $f(n)$ $O(f(n))$ Widzimy, że ta definicja jest równoważna naszej definicji pełnej konstruowania w czasie dla funkcji . $f(n)\geq (1+\epsilon)n$

P1:

$EXP-TIME=NEXP-TIME$ $L\in NEXP-TIME$ $L\subseteq\{0,1\}^*$ $k\in\mathbb{N}$ $L$ $M$ $2^{n^k-1}$ $M$

f (n) = {\begin{cases} 8 n + 2 & if (first ⌊ \sqrt[k]{⌊ \log n ⌋ + 1} ⌋ bits of b i n (n)) \in L \\ 8 n + 1 & else \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.$

$f$ $T$

$w$ $n$ $\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$ $O(n)$
$M$ $w$
$\left(M\textrm{ accepts using choices given by }w\right)$

$w$ $=n$ $M$ $\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$ $n$

$T$ $8n+1$ $f$

$w$ $n$ $T$ $8n$
$T$

$f$ $EXP-TIME=NEXP-TIME$

$L$

$x$ $n$ $x00\ldots 0$ $|x|^{k-1}$ $x=\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$
$f(n)$ $f(n)$

$L$ $L\in NEXP-TIME$ $EXP-TIME=NEXP-TIME$

— David G.
źródło

Bardzo dobrze! [wypełnienie, aby uszczęśliwić pole komentarza]

— Emil Jeřábek

Bardzo podobny pomysł do tego przedstawionego w odpowiedzi na zapytania Q1 służy również tutaj .

— David G