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:
“The feeling of being hurried is not usually the result of living a full life and having no time. It is on the contrary born of a vague fear that we are wasting our life. When we do not do the one thing we ought to do, we have no time for anything elsewe are the busiest people in the world.”
—Eric Hoffer (19021983)
“In a hierarchy every employee tends to rise to his level of incompetence.”
—Laurence J. Peter (19191990)
“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 (19131960)