Advertisement
Published in:
2016 | OriginalPaper | Chapter
15. Hierarchy Theorems
Author : Bernhard Reus
Published in: Limits of Computation
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
In this chapter we investigate the question whether we can decide more problems if we have more time available to do so. The corresponding positive results are called Hierarchy theorems as they establish a hierarchy of problem classes. We distinguish the case when the time bounds are linear and show for the
WHILE language restricted to one variable that larger constants allow for more problems to be decided. The version beyond linear time establishes a hierarchy between classes with specific time bounds, if one time bound grows much more quickly than the other.