Why does theoretical computer science draw the line at 'polynomial-time' for tractability?
Apolynomial functions are simpler to write than exponentials
Bthe SQL standard mandates polynomial-time queries
Cpolynomial functions stay feasible at large n; exponentials don't
Dall real-world hardware is polynomial-time, but quantum hardware is exponential
Answer & Solution
Correct answer: C. polynomial functions stay feasible at large n; exponentials don't
Cobham-Edmonds thesis: at n = 100, n² takes microseconds, 2^n takes longer than the universe's age. Polynomial scales tractably with input size; exponential blows past anything we can compute. The other options confuse simplicity of expression, SQL semantics, or hardware classes with the asymptotic feasibility argument.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhich set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined forThe running time and space of Floyd-Warshall on a graph with V vertices and E edges is