Comic #3866: p-np

View Original Comic

Description

Here is the transcription of the comic text:

Panel 1: “IT HAS BEEN SHOWN THAT ALL NP-HARD PROBLEMS ARE THE SAME. IF YOU’VE SOLVED ONE, YOU’VE SOLVED THEM ALL.”

Panel 2: “I PROPOSE A COROLLARY: IF YOU HAVE A STUPID SOLUTION TO ONE NP-HARD PROBLEM, IT STUPIDLY SOLVES THEM ALL. I CALL THIS ‘SULLOOSHUN’.”

Panel 3: “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?”

Panel 4: “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’.”

Panel 5: “SOLVED!”

Panel 6: “NOW, LET’S APPLY THIS SULLOOSHUN TO THE BIN-PACKING PROBLEM, WHICH CONCERNS HOW TO EFFICIENTLY PACK BOXES OF VARIOUS SIZES INTO BINS.”

Panel 7: “IF YOU COLLAPSE THE UNIVERSE, EVERYTHING IS THE SAME SIZE, AND ANYWAY, WHY BOTHER PACKING IF YOU CAN’T GO ANYWHERE?”

Panel 8: “SOLVED!”

Panel 9: “CONSIDER THE HALTING PROBLEM. IS THERE A GENERAL WAY TO TELL IF A PROGRAM WITH A GIVEN INPUT WILL EVER STOP?”

Panel 10: “THE SULLOOSHUN IS YES. IN THE SINGULARITY, TIME DOESN’T EXIST. THE PROGRAM CAN’T EVEN START, MUCH LESS STOP.”

Panel 11: “SOLVED!”

Panel 12: “DO YOU KNOW ANYTHING ABOUT MATHEMATICS?”

Panel 13: “THAT IS BEYOND THE SCOPE OF THIS TALK.”

Panel 14: (Background characters looking confused)

Feel free to ask if you need anything else!