[Teoria złożoności] Złożoność maszyny Turinga

[ixi2]

Rozważmy siedmiotaśmową deterministyczną maszynę Turinga akceptującą język \(\displaystyle{ L}\) - \(\displaystyle{ n}\)-literowe słowa tego języka - w czasie ograniczonym funkcją

\(\displaystyle{ T(n) = 2n^{3} + 1 > n}\)

Z jakim ograniczeniem czasowym może akceptować ten język pewna jednotaśmowa deterministyczna maszyna Turinga? Napisz wielomian funkcji ograniczenia czasowego.

Nie wiem czy dobrze rozumuję - powinienem cały ten wielomian podnieść do potęgi \(\displaystyle{ 2}\)?-- 8 kwi 2017, o 19:16 --x