Preskoči na glavno vsebino

David Gajser: Verifying time complexity of Turing machines

Datum objave: 23. 4. 2012
Seminar za teorijo grafov in algoritme
Četrtek 26. 4. 2012 ob 12:15 v predavalnici 3.05 na Jadranski 21
Two people, Andrej and Tomaž, have their own one-tape Turing machine. Andrej asserts, that his TM runs in time A(n) and Tomaž asserts that his TM runs in time T(n). Suppose A(n)=o(n log(n)) and T(n)=\Omega(n log(n)). We claim that Tomaž is able to verify Andrej's assertion, but Andrej has no algorithm to verify the assertion of Tomaž.