Which of the following best explains why P is called a 'robust' complexity class?
AProblems in P always run in under one second on modern hardware
BPolynomial-time solvability is preserved across reasonable computational models such as multi-tape TMs and random-access machines
CP contains only problems solvable in linear or quadratic time
DThe definition of P is equivalent to DTIME(n²)
Robustness means the membership of a language in P does not depend on whether you use a single-tape TM, a multi-tape TM, a random-access machine, or other reasonable deterministic models — simulating any one in another costs at most a polynomial overhead, which stays within P. This model-independence is what gives P its status as a meaningful, non-arbitrary boundary for tractability.
Question 2 True / False
A problem being in P guarantees that it can be solved efficiently in practice for any real-world input size.
TTrue
FFalse
Answer: False
P requires only that there *exists* a polynomial-time algorithm — but n^100 is polynomial. An algorithm with that exponent would be completely unusable for any real input, yet its language is in P. Conversely, algorithms outside P (e.g., exponential in the worst case) may be perfectly practical for small inputs or typical instances. 'In P' is a necessary but far from sufficient condition for practical efficiency.
Question 3 Short Answer
Why does complexity theory define 'efficiently solvable' as polynomial time rather than, say, quadratic or cubic time?
Think about your answer, then reveal below.
Model answer: Polynomial time is the right threshold because it is closed under composition: feeding the output of one polynomial-time algorithm into another produces a polynomial-time computation overall. It is also robust across reasonable computational models. Quadratic or cubic would not have this closure property and would be model-dependent. The class P thus marks a stable, machine-independent boundary that empirically separates most tractable problems from those that appear fundamentally hard.
The closure property is decisive: if algorithm A runs in O(n^a) and its output has polynomial length, feeding it into algorithm B running in O(m^b) gives a combined runtime of O(n^(ab)), still polynomial. This composability is what lets us build complex systems from P subroutines and stay in P. No smaller class like DTIME(n²) has this closure property in a model-independent way, which is why polynomial — not any specific polynomial — is the right threshold.