Questions: Polynomial-Time Computation and the Class P

Question 1

Which of the following correctly describes the class P?

• A. All problems that can be solved by a computer program, regardless of runtime
• B. All decision problems for which some deterministic Turing machine can produce the answer in time bounded by a polynomial in the input length
• C. All problems whose optimal algorithm runs in O(n²) or faster
• D. All problems that can be verified quickly once a solution is provided

Answer: (B)

P is the class of languages (equivalently, decision problems) for which *some* polynomial-time deterministic Turing machine exists. The definition is existential over algorithms — a problem is in P if at least one polynomial-time algorithm exists, not necessarily a specific famous one. Option A describes decidable problems (a much larger class). Option C conflates a problem's membership in P with the speed of a particular algorithm. Option D defines NP, not P.

Question 2

A proof that P = NP is discovered. Which consequence would most directly and immediately follow?

• A. All currently hard optimization problems would become trivially easy in practice, with no engineering effort
• B. RSA encryption and elliptic-curve cryptography would be theoretically broken, since their security rests on computational hardness assumptions that require P ≠ NP
• C. Sorting algorithms would become faster because P includes all polynomial-time problems
• D. Every algorithm would run in linear time because polynomial time would be equivalent to O(n)

Answer: (B)

Modern public-key cryptography (RSA, elliptic curves, Diffie-Hellman) is secure because it assumes certain problems (integer factorization, discrete logarithm) are hard — specifically, not solvable in polynomial time. These problems are in NP. If P = NP, they would also be in P, meaning efficient algorithms would exist in principle. The cryptographic systems would be theoretically broken. Note that 'theoretically broken' does not immediately mean 'practically broken' — a polynomial-time algorithm might have an enormous constant or high degree — but the theoretical foundation would collapse.

Question 3

P ⊆ NP: every problem in P is also in NP.

• T. True
• F. False

Answer: True

This follows immediately from the definitions. If a problem can be *solved* in polynomial time (P), then given a proposed solution, you can *verify* it in polynomial time by simply re-running the polynomial-time solver. NP requires only that verification is polynomial-time, so any P problem trivially qualifies. The open question is the other direction: whether NP ⊆ P — whether every problem easy to verify is also easy to solve.

Question 4

A problem is in P if a particular well-known algorithm for it runs in polynomial time.

• T. True
• F. False

Answer: False

Complexity theory classifies *problems*, not specific algorithms. A problem is in P if *any* polynomial-time algorithm exists for it — including algorithms not yet discovered or published. Conversely, if a specific algorithm runs in exponential time, that does not mean the problem is outside P; perhaps a better polynomial-time algorithm exists. This reframing from 'how fast is this algorithm?' to 'what is the intrinsic difficulty of this problem?' is the central conceptual move distinguishing complexity theory from algorithm analysis.

Question 5

What is the key conceptual shift from algorithm analysis to complexity theory, and why does this reframing matter for classifying problems?

Model answer: Algorithm analysis asks: how fast does *this specific algorithm* run on *this input*? Complexity theory asks: what is the intrinsic computational difficulty of *this problem* — is there *any* efficient algorithm, or is hardness inherent to the problem itself? A problem's membership in P (or NP) is a property of the problem, not of any particular algorithm. This matters because it allows us to prove lower bounds: if a problem is outside P (assuming P ≠ NP), then no polynomial-time algorithm can exist, not merely that we haven't found one yet. This separates 'we haven't been clever enough yet' from 'no cleverness can help.'

The shift is from existential ('does this algorithm work?') to universal ('is there any algorithm that works?'). It enables the theory of NP-completeness: showing that a problem is NP-complete means it is at least as hard as every problem in NP, so a polynomial-time algorithm for it would imply P = NP and solve all NP problems simultaneously. This gives problems a meaningful classification based on their inherent difficulty, independent of the state of human ingenuity.