Emulacja Oblivious Turing Machine w dolnej granicy

Czy istnieje dowód, że emulacji maszyny Turinga na nieświadomej maszynie Turinga nie można wykonać w mniej niż gdzie jest liczbą kroków, które wykonuje maszyna Turinga ? Czy to tylko górna granica? $\mathcal{O}\left(m\log m\right)$ $m$

W artykule Paula Vitányi o relatywizowanych, nieświadomych maszynach Turinga, twierdzi Vitányi

„Oni [ Pippenger i Fischer, 1979 ] wykazali, że tego wyniku nie można ogólnie poprawić, ponieważ istnieje język L, który jest rozpoznawany przez 1-taśmową maszynę Turinga czasie rzeczywistym , i każdą nieświadomą maszynę Turinga rozpoznającą musi użyj co najmniej kroku kroków ". $M$ $M'$ $L$ $O(n \log n)$

Powinno to oznaczać jako bezwzględną granicę. Nie znalazłem jednak na to żadnego dowodu $O(m \log m)$

Pippenger, Nicholas; Fischer, Michael J. , Relacje między miarami złożoności , J. Assoc. Comput. Mach. 26, 361–381 (1979). ZBL0405.68041 .

Jakieś pomysły? Ponadto, jaka jest złożoność przestrzenna tej emulacji? O ile wiem, konwersja na uniwersalną maszynę Turinga podwaja tylko długość taśmy. Czy mogę założyć, że złożoność przestrzeni to przy złożoności przestrzeni oryginalnej maszyny Turinga? $\mathcal{O}\left(l\right)$ $l$

cc.complexity-theory turing-machines

— Willem Van Onsem
źródło

Dopasuj nawiasy i określ, co to jest T. Myślę, że wciąż jest otwarty, ale nie jestem ekspertem.

— Tsuyoshi Ito,

czym jest nieświadoma maszyna Turinga?

— Suresh Venkat

Oblivious Turing Machine to maszyna Turinga, w której ruch głowic zależy tylko od długości wejścia, a nie od samego wejścia. Na przykład wyszukiwanie liniowe (jeśli głowa porusza się, dopóki nie osiągnie końca wejścia)

— Willem Van Onsem

Odpowiedzi:

Jak wspomniano powyżej, ogólnie nie wiadomo, czy istnieje szybsza nieświadoma symulacja.

Ale ciekawe dolne granice tego problemu są znane w bardziej ograniczonych warunkach. Na przykład, co jeśli chcesz niepomny symulacja który zachowuje nie tylko czas , ale także wykorzystanie miejsca ? Beame i Machmouchi udowodnili ostatnio, że interesujący kompromis czasoprzestrzenny jest niższy dla tego problemu: albo przestrzeń musi wzrosnąć o współczynnik , albo czas musi wzrosnąć o współczynnik . $t$ $s$ $n^{1-o(1)}$ $\Omega(\log n \cdot \log \log n)$

Artykuł jest tutaj: http://eccc.hpi-web.de/report/2010/104/

— Ryan Williams
źródło

Tylko rozszerzony komentarz: Myślę, że wciąż jest to otwarty problem; zajrzyj na blog Liptona i Regana, aby znaleźć ciekawe dyskusje na temat poprawy wyników twierdzenia Fischera-Pippengera .

Na przykład zobacz posty: Oblivious Turing Machines and a „Crock” or Circuits Bounds for Turing Machine Computations (oba datowane na 2009 rok).

W drugim poście pokazują, że lepsze ograniczenie obwodu ( ) jest możliwe przy użyciu funkcji częściowej wartości logicznej która jest przybliżona oryginalna funkcja na wejściach . $O(n \log {\log n})$ $g:2^n \to \{0,1,*\}$ $f$ $2^{n-o(n)}$

— Marzio De Biasi
źródło

Przeczytałem twierdzenie Fischera-Pippengera i jest to dowód. Jednak nigdy w dowodzie nie ma elementu, który mówi, że nie ma szybszej metody. Zastanawiałem się, czy istnieje dowód, że jest to gwarantowane minimum. Jeśli spojrzysz na dowód, emulują one TM na UTM, a następnie wykonują mały hack, aby to nieświadomie. Można jednak argumentować, że pierwszy krok jest niezbędny, aby wiedzieć, jak zachowa się maszyna.

— Willem Van Onsem

@CommuSoft Nikt nie sugeruje, że dowód jest niczym innym, jak dowodem z górnej granicy. Wpisy na blogu sugerują, że ulepszanie Fischera-Pippengera to otwarty problem.

— Sasho Nikolov

@CommuSoft: Jest to otwarty problem ... być może istnieje szybsza metoda lub ktoś udowodni, że jest to najlepsza możliwa do osiągnięcia.

— Marzio De Biasi

Cóż, czytam artykuł opublikowany przez Paula Vitányi zatytułowany „Relatywistyczna nieświadomość”, który wydaje się twierdzić, że czas wynosi co najmniej O (m log m). Jednak nie jestem jeszcze pewien, czy użyje twierdzenia Fischera-Pippengera, aby to udowodnić.

— Willem Van Onsem,