An algorithm for a decision problem runs in O(n^100) time on inputs of length n. Which of the following is correct?
AThe problem is not in P because n^100 grows too fast to be considered efficient
BThe problem is in P, but this tells us nothing about whether the algorithm is practical
CThe problem is in P and is therefore efficiently solvable for large inputs
DWhether the problem is in P depends on the specific machine model used to run the algorithm
P is defined by the existence of a polynomial-time algorithm, not by practical efficiency. n^100 is a polynomial, so the problem is in P. But P membership does not guarantee practicality — n^100 is completely useless for any real input. The significance of P is theoretical robustness and a robust threshold for tractability, not a guarantee that polynomial = fast. This is the central misconception the definition is designed to resist.
Question 2 Multiple Choice
Why is 'polynomial time' specifically chosen as the defining boundary for class P, rather than a more restrictive class like O(n²) or O(n log n)?
APolynomial time was chosen because most practical algorithms run in quadratic or sub-quadratic time
BThe polynomial boundary is closed under composition and is model-independent: a polynomial of a polynomial is still a polynomial, and all standard computational models agree on it
CPolynomial time was chosen by convention after Cobham's thesis, without strong theoretical justification
DThe boundary corresponds exactly to problems solvable on physical hardware within the age of the universe
The key property is robustness. Polynomials are closed under composition: if algorithm A calls subroutine B, and both run in polynomial time, the whole thing runs in polynomial time. More importantly, switching between standard computational models (single-tape TM, multi-tape TM, RAM) can multiply running time by a polynomial factor — but a polynomial times a polynomial is still a polynomial. This makes P invariant across all standard models of deterministic computation, unlike any fixed bound like O(n²).
Question 3 True / False
A problem in P can usually be solved efficiently in practice, regardless of the degree of the polynomial.
TTrue
FFalse
Answer: False
P membership is a theoretical classification, not a practical guarantee. An algorithm running in n^50 time is in P but completely impractical for any non-trivial input. The importance of P is its robustness as a complexity class — the fact that polynomial time is model-independent and closed under composition — not that all polynomial-time algorithms are fast. In practice, algorithms with degree > 4 or 5 are often replaced by heuristics.
Question 4 True / False
If a problem is shown to be in P using a multi-tape Turing machine, it is also in P for a single-tape Turing machine.
TTrue
FFalse
Answer: True
This is precisely the robustness property of P. Converting a multi-tape TM to a single-tape TM can square the running time, but a polynomial squared is still a polynomial. All standard deterministic models of computation — single-tape TMs, multi-tape TMs, random-access machines, Boolean circuits — agree on which problems are in P. This model-independence is what makes P a fundamental class rather than an artifact of one particular machine model.
Question 5 Short Answer
What is the theoretical significance of P, given that some problems in P (like one running in n^100 time) are completely impractical?
Think about your answer, then reveal below.
Model answer: P's significance is its robustness as a complexity class: it is closed under composition, closed under simulation between standard computational models, and captures a stable, model-independent notion of efficient computability. It forms a meaningful boundary because all standard deterministic models agree on it, and it contrasts sharply with problems requiring exponential time. P is a theoretical threshold, not a practical guarantee — it rules out inherent intractability even if the constant or degree matters enormously in practice.
The point of P is to identify problems that can be solved by a systematic deterministic procedure (not brute-force search), as opposed to problems like NP-complete ones that seem to require exponential exploration. The contrast between P and NP — between finding and verifying — is where P's definition earns its keep. Whether P = NP is the most important open problem in CS precisely because the distinction between these two classes is so fundamental.