3 ms·

P != quickly solvable by a classical computer. P means solvable in polynomial time relative to the size of the problem, which could still take longer than the

• deleted 8y ago
  [deleted]
• doubleunplussed 8y ago
  Given that computer scientists use the word "efficiently" to mean "in polynomial time", I'm not too upset at using "quickly" to mean the same.
  • skate22 8y ago
    Idk, I majored in CS and I don't use the term efficient or quick to imply relative asymptotic time complexity. Consider for example a randomized quicksort (O(n^2) worst case) is often faster than say mergesort (O(nlog(n)) worst case)) for small lists due to reduced overhead. I know these are both polynomial, but relatively speaking, randomized quicksort can be more efficient & quick. In the real world we can make certain assumptions about our problem domain, where the most 'efficient' solution for your business problem may not have the smallest asymptotic time complexity. Maybe it's fair to assume everyone reading this article knows what the auther means & i'm just being that guy, but I still don't like ambiguity lol
    • doubleunplussed 8y ago
      It's used when talking about the extended Church-Turing thesis [1]: > "A probabilistic Turing machine can efficiently simulate any realistic model of computation." The word 'efficiently' here means up to polynomial-time reductions. Real-world efficiency doesn't necessarily factor into what theoretical computer scientists are interested in. [1] https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis