Question 71
In time complexity theory, what is DTIME(t(n))?
Detailed Solution
DTIME(t(n)) bounds deterministic sequential execution time to function t(n) of input size n.
✓ Saved
Bihar STET – TOC Practice Test | Set 2
Your score
0/100
0 answered
Correct 0
Incorrect 0
Unanswered 100
Accuracy 0%
Question 72
In time complexity theory, what is NTIME(t(n))?
Detailed Solution
NTIME(t(n)) bounds the maximum depth of a nondeterministic execution tree to t(n).
✓ Saved
Question 73
How is the complexity class 'P' defined in terms of DTIME?
Detailed Solution
Class P represents the union of all deterministic polynomial time complexity classes DTIME($n^k)$ for integer k $\ge 1$.
✓ Saved
Question 74
How is the complexity class 'NP' defined in terms of NTIME?
Detailed Solution
Class NP represents the union of all nondeterministic polynomial time complexity classes NTIME($n^k)$ for integer k $\ge 1$.
✓ Saved
Question 75
What is 'Savitch's Theorem' in space complexity theory?
Detailed Solution
Savitch's Theorem proves that a deterministic TM can simulate a nondeterministic space-bounded TM with at most quadratic space overhead.
✓ Saved