Difference between revisions of "Main Page"
(→Rules) |
m (Protected "Main Page": Excessive vandalism ([Edit=Allow only administrators] (indefinite) [Move=Allow only administrators] (indefinite))) |
||
(123 intermediate revisions by 12 users not shown) | |||
Line 1: | Line 1: | ||
− | ''Welcome to the | + | __NOTOC__{{DISPLAYTITLE:explain xkcd}} |
+ | <center> | ||
+ | <font size=5px>''Welcome to the '''explain [[xkcd]]''' wiki!''</font><br> | ||
+ | We have an explanation for all [[:Category:All comics|'''{{#expr:{{PAGESINCAT:All comics|R}}-1}}''' xkcd comics]], | ||
+ | <!-- Note: the -1 in the calculation above is to discount "comic" 404, | ||
+ | which is not really a comic, even though we've categorised it so. --> | ||
+ | and only {{PAGESINCAT:Incomplete explanations|R}} | ||
+ | ({{#expr: {{PAGESINCAT:Incomplete explanations|R}} / {{LATESTCOMIC}} * 100 round 0}}%) [[:Category:Incomplete explanations|are incomplete]]. Help us finish them! | ||
+ | </center> | ||
+ | == Latest comic == | ||
+ | <div style="border:1px solid grey; background:#eee; padding:1em;"> | ||
+ | <span style="float:right;">[[{{LATESTCOMIC}}|'''Go to this comic explanation''']]</span> | ||
+ | <br clear="right"> | ||
+ | {{:{{LATESTCOMIC}}}}</div> | ||
− | + | <small>''Is this out of date? {{Purge|Clicking here will fix that}}.''</small> | |
− | == | + | == New here? == |
− | + | <div style="float:right; margin: 0 0 1em 1em">{{Special:ContributionScores/10/7/nosort,notools}}<div style="font-size:0.85em; width:25em; font-style:italic">[[Special:ContributionScores|Lots of people]] contribute to make this wiki a success. Many of the recent contributors, listed above, have [http://www.explainxkcd.com/wiki/index.php?title=Special%3AContributions&contribs=newbie just joined]. You can do it too! Create your account [[Special:UserLogin/signup|here]].</div></div> | |
− | |||
− | |||
− | + | You can read a brief introduction about this wiki at [[explain xkcd]]. Feel free to [[Special:UserLogin/signup|sign up for an account]] and contribute to the wiki! We need explanations for [[:Category:Incomplete explanations|comics]], [[:Category:Characters|characters]], [[:Category:Comics by topic|themes]] and [[:Category:Meta|everything in between]]. If it is referenced in an [[xkcd]] web comic, it should be here. | |
− | |||
− | + | * If you're new to wiki editing, see the [[explain xkcd:Editor FAQ]] for a specific guidance to this Wiki and the more general help on [[mw:Help:Editing pages|how to edit wiki pages]]. There's also a handy {{w|Help:Cheatsheet|wikicode cheatsheet}}. | |
− | + | * Discussion about the wiki itself happens at the [[explain xkcd:Community portal|Community portal]]. | |
− | + | * You can browse the comics from [[List of all comics]] or by navigating the category tree at [[:Category:Comics]]. | |
− | + | * There are incomplete explanations listed [[:Category:Incomplete explanations|here]]. Feel free to help out by expanding them! | |
− | + | == Rules == | |
− | + | Don't be a jerk! | |
− | + | There are a lot of comics that don't have set-in-stone explanations; feel free to put multiple interpretations in the wiki page for each comic. | |
− | + | If you want to talk about a specific comic, use its discussion page. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | Please only submit material directly related to (and helping everyone better understand) xkcd... and of course ''only'' submit material that can legally be posted (and freely edited). Off-topic or other inappropriate content is subject to removal or modification at admin discretion, and users who repeatedly post such content will be blocked. | |
− | If you | + | If you need assistance from an [[explain xkcd:Administrators|admin]], post a message to the [[explain xkcd:Community portal/Admin requests|Admin requests]] board. |
− | + | [[Category:Root category]] | |
− | [[ |
Latest revision as of 07:50, 17 April 2024
Welcome to the explain xkcd wiki!
We have an explanation for all 2939 xkcd comics,
and only 10
(0%) are incomplete. Help us finish them!
Latest comic
Complexity Analysis |
Title text: PERPETUALLY OPTIMISTIC CASE: Early in the execution, our research group makes a breakthrough on proving P=NP. |
Explanation
This explanation may be incomplete or incorrect: Created by a PERPETUALLY OPTIMISTIC BOT - Please change this comment when editing this page. Do NOT delete this tag too soon. |
Cueball is teaching about an algorithm's complexity. The average-case runtime of the algorithm is written as O(n log n), in Big O notation, expressing the asymptotic runtime of the algorithm as the number of inputs to it grows larger and larger. This is an error by Randall (or Cueball), as Big-O notation represents only the worst-case, not average-case time complexity.
The "best case" for an algorithm is typically its runtime when its inputs have optimal values and it runs in as little time as possible. The joke here is that not only does it run this quickly, but that its runtime is actually an hour shorter because of an act of Congress changing daylight saving time, potentially giving it negative 'runtime'. Daylight saving time is a recurrent theme on xkcd, and it is clear that Randall is not a fan. so that congress just gives us an hour in a surprise DST is another way for Randall to mock the concept.
The "worst case" refers to the movie Groundhog Day, in which the same events occur over and over in a sort of time loop. And thus if the hardware running the algorithm is stuck in this kind of loop that resets to a previous time before it ever gets finished then the algorithm would never terminate. In the movie we must expect that the whole world is reset after every day, and not just the city where the movie takes place. But if it is just a town outside the rest of the world, where you can still connect to their hardware from outside, then this situation could arise. For those in the town, the algorithm never uses much time, since they do not experience the reset of the day. That was only the main character who lived the same day over and over. For all other in the movie it was their first time living that day, every day. And if the main character did nothing everyone else would have the same day over and over.
This may be an indirect reference to the halting problem, a famous problem in computer science of determining whether a given algorithm will ever halt. The halting problem is undecidable, meaning that there is no general algorithm that can tell whether a given algorithm will halt. The movie has been referenced before in 1076: Groundhog Day.
The title text refers to perhaps an even more famous problem in computer science, P versus NP. This asks whether every problem whose solution can be quickly verified (in nondeterministic polynomial time, NP) can also be quickly solved (in polynomial time, P). The P-versus-NP problem is one of the seven Millennium Prize Problems, and as such has a $1 million prize for its solution. Presumably, the problem discussed here is in NP, so if P=NP, its worst-case runtime would be some polynomial O(nk). However, P vs. NP is a Millennium Prize Problem for a reason, and most computer scientists expect that P != NP, so hoping for a breakthrough in proving P=NP is "perpetually optimistic".
Transcript
- [Cueball is holding a presentation pointer stick, pointing to a table behind him that towers above him. The table has a heading above it and then two columns and three rows. the first column is slim and the second much broader.]
- Results of algorithm complexity analysis:
Average case O(n log n) Best case Algorithm turns out to be unnecessary and is halted, then Congress enacts surprise daylight saving time and we gain an hour Worst case Town in which hardware is located enters a Groundhog Day scenario, algorithm never terminates
Is this out of date?
.New here?
Last 7 days (Top 10) |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
You can read a brief introduction about this wiki at explain xkcd. Feel free to sign up for an account and contribute to the wiki! We need explanations for comics, characters, themes and everything in between. If it is referenced in an xkcd web comic, it should be here.
- If you're new to wiki editing, see the explain xkcd:Editor FAQ for a specific guidance to this Wiki and the more general help on how to edit wiki pages. There's also a handy wikicode cheatsheet.
- Discussion about the wiki itself happens at the Community portal.
- You can browse the comics from List of all comics or by navigating the category tree at Category:Comics.
- There are incomplete explanations listed here. Feel free to help out by expanding them!
Rules
Don't be a jerk!
There are a lot of comics that don't have set-in-stone explanations; feel free to put multiple interpretations in the wiki page for each comic.
If you want to talk about a specific comic, use its discussion page.
Please only submit material directly related to (and helping everyone better understand) xkcd... and of course only submit material that can legally be posted (and freely edited). Off-topic or other inappropriate content is subject to removal or modification at admin discretion, and users who repeatedly post such content will be blocked.
If you need assistance from an admin, post a message to the Admin requests board.