Non-deterministic Time Hierarchy Theorem
If g(n) is a time-constructible function, and f(n+1) = o(g(n)), then there exists a decision problem which cannot be solved in non-deterministic time f(n) but can be solved in non-deterministic time g(n). In other words, the complexity class NTIME(f(n)) is a strict subset of NTIME(g(n)).
Read more about this topic: Time Hierarchy Theorem
Famous quotes containing the words time, hierarchy and/or theorem:
“Husband,
who am I to reject the naming of foods
in a time of famine?”
—Anne Sexton (1928–1974)
“In a hierarchy every employee tends to rise to his level of incompetence.”
—Laurence J. Peter (1919–1990)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)