Czy granice środowiska wykonawczego są rozstrzygalne dla czegoś nietrywialnego?

Problem   Biorąc pod uwagę maszynę Turinga która zna czas działania O ( g ( n ) ) w odniesieniu do długości wejściowej n , czy czas działania M ∈ O ( f ( n ) ) ?$M$${O}(g(n))$$n$$M \in {O}(f(n))$

Czy powyższy problem jest rozstrzygalny dla niektórych niebrywalnych par i f ? Rozwiązanie jest trywialne, jeśli g ( n ) ∈ O ( f ( n ) ) .$g$$f$$g(n) \in O(f(n))$

Jest to związane z problemem Czy granice środowiska wykonawczego w P są rozstrzygalne? (odpowiedź: nie) . Można wyprowadzić z odpowiedzi Viola , że jeśli i f ( n ) ∉ O ( g ( n ) ), to problem jest nierozstrzygalnym.$f(n)\not \in o(n)$$f(n)\not \in O(g(n))$

Wymaganie, aby było spowodowane tym, że M ' w dowodzie Violi potrzebuje O ( n ) czasu, aby znaleźć swój rozmiar wejściowy. Dlatego dowód Violi nie mógł działać, gdy f ( n ) = 1 .$f(n)\not \in o(n)$$M'$$O(n)$$f(n)=1$

Byłoby interesujące, gdybyśmy mogli zdecydować o czasie działania algorytmów czasu podliniowego. Szczególnym przypadkiem jest, gdy mamy dowolnego i f ( n ) = 1 .$g(n)$$f(n)=1$

Oto kilka uwag, które mogą być istotne:

1. Kobayashi udowodnił, że TM działająca w czasie akceptuje zwykły język (a więc działa w czasie O ( n ) ); ostatnio zostało to rozszerzone na niedeterministyczne TM ( Tadaki, Yamakami i Lin ).$o(n\log n)$$O(n)$
2. Maszyny działające w czasie faktycznie działają w stałym czasie (rozważ dowolne n, dla którego czas działania jest krótszy niż n ; dodanie znaków na końcu nie wpływa na TM).$o(n)$$n$$n$