Content deleted Content added
→Proof: period |
Add statement that similar theorems are not known for probabilistic time or for quantum time (reference is from Rudich complexity book, don't have it with me) |
||
Line 55:
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'')).
== Extensions to other time resources ==
Similar theorems are not known for [[probabilistic time]] or [[quantum time]] {{fact}}.
==Consequences==
| |||