## xkcd on science and math

(Only marginally related to linguistics.)

Two xkcd cartoons from the world of science (the fundamental forces of physics) and math/computer science (NP-complete problems):

(#1)

(#2)

Fundamental Forces. In #1 Fundamental Forces (xkcd 1489), the narrator starts out boldly and then winds down. Presumably aiming for somethin like this Wikipedia overview:

Fundamental interactions, also known as fundamental forces or interactive forces, are the interactions in physical systems that appear not to be reducible to more basic interactions. There are four conventionally accepted fundamental interactions — gravitational, electromagnetic, strong nuclear, and weak nuclear — each understood as the dynamics of a field.

And then the details become mind-boggingly complex (and not particularly amenable to chalkboard exposition).

NP-Complete. In #2 NP-Complete (xkcd 287), the strip skirts another very complex matter, where the standard terminology is not especially easy to cope with. To start with, the NP here stands for ‘nondeterministic polynomial time’; NP-complete names a class of particularly difficult problems. From Wikipedia:

Although any given solution to an NP-complete problem can be verified quickly (in polynomial time), there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a consequence, determining whether or not it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today.

(This is actually a simple account of the matter.)

On to #2. The problem set up there is a well-known NP-complete problem:

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. (Wikipedia link)

The cartoon also alludes to another famous NP-complete problem:

The travelling salesman problem (TSP) asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? (Wikipedia link)

The main Wikipedia page alludes to the P versus NP problem, which offers the possibility that one of the NP-complete completes can in fact be solved quickly — in (ordinary) polynomial time. If any one of them is, then they all are; there’s a sense in which all the enormous number of NP-complete problems are really the same problem, despite their different appearances.

Not something that can be easily communicated in a cartoon.

### 2 Responses to “xkcd on science and math”

1. John Baker Says:

In the first cartoon, you omitted the excellent tooltip text: “”Of these four forces, there’s one we don’t really understand.” “Is it the weak force or the strong–” “It’s gravity.””

For the second cartoon (tooltip text: “General solutions get you a 50% tip”), it would serve the patrons right if the server then brought them seven mixed fruit appetizers. I got that answer fairly quickly and didn’t bother figuring out if there is another, but someone else was more diligent, and according to Explain XKCD, http://www.explainxkcd.com/wiki/index.php/287, they intended to order a combination of two orders of hot wings, one order of mixed fruit, and one sampler plate.