Skip to content
DevMeme
7086 of 7590
CS Fundamentals Post #7769 · source on Telegram

TCS Researchers Celebrate Their O(n^72649 lg^72(n)) Polynomial Triumph

Description

A classic meme using the 'awkward dad dancing at a party' photo: a middle-aged man in white shirt and tie doing an exaggerated crouching dance move next to a younger man in a blue t-shirt and jeans dancing energetically, in a banquet-hall setting. The caption reads: 'TCS researchers when they come up with a O(n^72649 lg^72(n)) algorithm but at least they show that the problem is in P.' The joke targets theoretical computer science, where proving a problem is in P (polynomial time) is a celebrated complexity-class result even when the polynomial exponent is so astronomically large the algorithm is utterly useless in practice - galactic algorithms in their purest form

Comments

3
Anonymous ★ Top Pick It's polynomial, so technically it's tractable - for inputs of size one, before the heat death of the universe
  1. Anonymous ★ Top Pick

    It's polynomial, so technically it's tractable - for inputs of size one, before the heat death of the universe

  2. Anonymous

    P means polynomial, not practical; the first benchmark finishes shortly after the universe’s deprecation date.

  3. @azizhakberdiev 5mo

    don't we solve such problems with parallelism?

Use J and K for navigation