Computational complexity

Iris: what does P = NP mean?
Mary: "Though the universe's mysteries appear deep, their depth is an illusion. The world is nothing but a toy based on a magic trick."
.
Iris: like this? [holds up the infinite light vortex]
Mary: Yes. Exactly.
.
Iris: what's the big deal about it? i thought it was something to do with maths and computers.
Mary: If P = NP, there's a trick by which you can factor 55006097 as easily as you can multiply 4133 and 13309.
Iris: [sarcastically] earth-shattering.
.
Mary: More generally, you could prove any mathematical conjecture as easily as checking the logic of such a proof, were the proof to already exist.
Iris: [Iris makes a so-so gesture] okay, slightly troubling.
.
Mary: If P = NP, there's trick that will make you as clever as anything you could understand
.
Mary: As talented as anything you could appreciate
.
Mary: As funny as—
Iris: [no longer sarcastic] okay, sarcasm withdrawn
.
Iris: so, what are P and NP?
Mary: P and NP are computational complexity classes.
.
Mary: P stands for "Polynomial time". It's the class of problems whose solutions require a computation with a length that has at most a polynomial ratio to the size of the input.
.
.
Iris: like, if sudoku puzzles take a computer X^3 steps to solve, maximum, that's polynomial time?
Iris: where X is the size of the grid or whatever?
.
Mary: Yes. Whereas if the most efficient solution takes 3^X steps, that's exponential time.
Iris: ok, seems simple enough...
.
Mary: Computational complexity theorists have yet to establish whether Sudoku can be solved in polynomial time. As with many puzzles, they do know it belongs to the class of problems whose solutions can be verified in polynomial time.
Mary: Additionally, they know that if it can be solved in polynomial time, everything else in the class can as well.
.
Iris: what's the sudoku class called?
Mary: NP.
.
Iris: oh.
Iris: i'm starting to get a creepy feeling
.
Iris: i assume the maxcut problem is also in NP
Mary: Yes. Like Sudoku, it's "NP-complete". If it's solvable in polynomial time...
.
Iris: ...then P = NP. that explains grant's obsession with that algorithm...
.
Iris: christ, i feel unclean for working on it with him.
.
Iris: it's like helping a friend of a friend look for their car based on a verbal description with subtly suspicious holes in it, eventually giving up, then later watching Back to the Future and realizing what car they were looking for
.
Iris: in retrospect, it's obvious ben has known all along that grant's algorithm can't work, and has politely omitted that detail every time he's discussed it with me
.
Iris: [as Ben] Ah yes, Grant is obsessed with his car. He often asks me to help him find it in the car park.
.
Iris: never actually _suggesting_ that i help grant with his algorithm, just letting the idea sit quietly on the table like a vase of wilted poppies...
.
.
Iris: i assume the university types are busy proving P _doesn't_ equal NP.
Mary: Yes. Trying, at any rate.
.
Iris: how long have they been at it?
Mary: 40 years.
.
Iris: why is it taking so long?
Iris: and don't say "i don't know" because that's the scariest thing i can imagine you saying
Mary: About this, or generally?
Iris: about anything!
.
Mary: Were you scared all the time before you met me, when you had to figure things out yourself?
Iris: no! because i didn't hang out with hp lovecraft's robot mindfuck squad all day!
.
Hawaii: can i be in hp lovecraft's robot mindfuck squad?
Iris: YOU *ARE* HP LOVECRAFT'S ROBOT MINDFUCK SQUAD! I SHOULD PROBABLY STOP *SCREAMING* "MINDFUCK" AT AN *EIGHT-YEAR-OLD!*