Home > News > David Gajser: Kako preveriti, ali je nek 1-tračni Turingov stroj časovne zahtevnosti C n + D?

David Gajser: Kako preveriti, ali je nek 1-tračni Turingov stroj časovne zahtevnosti C n + D?

Date: 17. 12. 2012
Source: Mathematics and theoretical computing seminar
Torek, 18. 12. 2012, od 12h do 14h, Plemljev seminar, Jadranska 19

Povzetek. Pogledali si bomo algoritem, ki preveri, ali je dani 1-tračni Turingov stroj časovne zahtevnosti C n + D za vnaprej podani naravni števili C in D. Spomnimo se, da noben algoritem ne zna preveriti, ali je dani 1-tračni Turingov stroj konstantne časovne zahtevnosti.

Vabljeni!