Content deleted Content added
m sp |
m =Non-deterministic time hierarchy theorem= lk |
||
Line 58:
== Non-deterministic time hierarchy theorem ==
If ''g''(''n'') is a time-constructible function, and ''f''(''n''+1) = [[Big O notation|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'')).
|