A note on time hierarchies for reasonable semantic classes without advice

2017/11/29 by Hao Wu, Wu, Hao
Computer Science · #semigroups and automata theory #Computability, Logic, AI Algorithms #Machine Learning and Algorithms

paper · pdf · doi:10.48550/arxiv.1711.11158

Abstract

We show time hierarchies for reasonable semantic classes without advice by eliminating the constant bits of advice in previous results.The elimination is done by a contrapositive argument that for any reasonable computational model,let CTIME(f(n))/g(n) denote the set of all languages decide by machines running in time O(f(n)) with advice of g(n) bits in that model, if CTIME(t(n))⊆ CTIME(T(n))/A(n) then CTIME(t(n))/a ⊆ CTIME(T(n))/a+2^aA(n) where a is a constant integer.

Related

• A Generic Time Hierarchy for Semantic Models With One Bit of Advice
• Alternating Hierarchies for Time-Space Tradeoffs
• A Predicative Harmonization of the Time and Provable Hierarchies
• Proper Hierarchies in Polylogarithmic Time and Absence of Complete\n Problems
• Comparing the power of advice strings: a notion of complexity for infinite words