P-np

|< < Prev Comic #3954 (December 12, 2015) Next > >|

p-np

Title text: Ironically, in the first draft of this comic, I misspelled Sullooshun.

Votey

Explanation

This explanation is either missing or incomplete.

Transcript

This transcript was generated by a bot: The text was scraped using AWS's Textract, which may have errors. Complete transcripts describe what happens in each panel — here are some good examples to get you started (1) (2).

[Describe panel here]

11 ha5 been shown that all np-hard problems are the same. If you've

- -if you have a stupid solution to one np-hard problem, it stupidly solves them all I call this a sullooshun:

Solved one, you've solved them all

Sullooshun

For instance the traveling salesman problem. A salesman has to visit a lot of cities, once each, then go home. What's the shortest route?

Well, if you collapse the universe into a singularity there's only ever one route. So, the sullooshun to every traveling salesman problem is "collapse the universe.

Solved

Now, let's apply this sullooshon to the bin-packing problem, which concerns how to efficiently pack boxes of various sizes

Into bins.

If you collapse the universe, everything is the same size, and anyway, why bother

Solved!

Packing if you cant go anywhere?

Consider the halting problem. Is there a

The sullooshun is yes. In the singularity, time doesn't exist. The program can't even start, much less stop.

General way to tell if a program with a given

Input will ever stop?

Do you know anything about mathematics?

Solved?

That is beyond

N

The scope of

Votey Transcript

This transcript was generated by a bot: The text was scraped using AWS's Textract, which may have errors. Complete transcripts describe what happens in each panel — here are some good examples to get you started (1) (2).

[Describe panel here]

I'll make your face a singularity

 add a comment! ⋅  add a topic (use sparingly)! ⋅  refresh comments!

Discussion

No comments yet!