Praveen2710 Posted February 20, 2014 Posted February 20, 2014 Hi I have an assignment question which I have no clue on how to start.I am posting the question. I would really appreciate if someone could guide me on how to solve it. Question: Show that for every time-constructible T: N → N, if L ∈ DTIME(T(n)), then there is an oblivious TM that decides L in time O(T (n) log T (n)). Any material that will help solve it or any similar examples would be highly appreciated.
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now