Równoważne definicje konstruowania czasu

Mówimy, że funkcja jest konstruowalna w czasie , jeśli istnieje deterministyczna wielopasmowa maszyna Turinga M, która na wszystkich wejściach długości n wykonuje co najwyżej f ( n ) kroki i dla każdego n istnieje pewien wkład długość n, na której M wykonuje dokładnie f ( n ) 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 M, która na wszystkich wejściach długości n wykonuje dokładnie f ( n ) 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 P ≠ N P ? 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.

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 ϵ > 0 st f ( n ) ≥ ( 1 + ϵ ) n , jest w pełni konstruowalna w czasie, jeśli jest obliczalny w czasie O ( f ( n ) ) . (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: 2 n ,$f:\mathbb{N}\rightarrow\mathbb{N}$$\epsilon>0$$f(n)\geq (1+\epsilon)n$$O(f(n))$$2^n$ , n ! , n ⌊ log n ⌋ , wszystkie wielomiany p ponad N st p ( n ) ≥ ( 1 + ϵ ) n ... Kobayashi również wykazał pełną konstruowalność czasową dla niektórych funkcji, które rosną wolniej niż ( 1 + ϵ ) n , jak n + ⌊ ⌊ log n ⌋ q ⌋ dla q ∈ Q + ...$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 f 2 są w pełni konstruowalne w czasie, to f 1 + f 2 , f 1 f 2 , f f 2 1 i f 1 ∘ f 2 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 M, która, biorąc pod uwagę ciąg 1 n , wyprowadza f ( n ) w czasie O ( f ( n ) ) . $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)=\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$