3 ms·
And yet it never uses the word "polynomial".
by EA 3y ago
And yet it never uses the word "polynomial".
- svat 3y agoIt uses "efficient" everywhere, only alluding to polynomial-time here: > Theoretical computer scientists use a technical definition for “efficient” that can be debated, but it serves as a useful proxy for the colloquial concept. The idea that “polynomial-time” and “efficient” are reasonable proxies for each other is the Cobham–Edmonds thesis: https://en.wikipedia.org/wiki/Cobham%27s_thesis https://en.wikipedia.org/wiki/Cobham%27s_thesis
- krackers 3y agoI don't see how this statement is useful, because if an alg is "tractable" iff it is poly-time then n^10 algorithms would be considered "tractable". I think the real reason we care about P in a CS-theoretic sense is because it's a closed group under various operations, which allows us to talk about things in an implementation-oblivious fashion. In practice in the real world we care only about low-degree P though (usually n < 3 at most), are really interested in linear & nlogn, and care about constant factors. There's also Quasi-Polynomial time algorithms which are interesting because they straddle the line between P and EXPTIME.