Well, just take n=1...right?

May 4, 2011 9:21 AM

In the afternoon of May 4, 1971, in the Stouffer's Somerset Inn in Shaker Heights, Ohio, Steve Cook presented his STOC paper proving that Satisfiability is NP-complete and Tautology is NP-hard.

40 years ago today, Cook presented his paper on the problem we know today as the "P v. NP" problem, or the hypothesis "P = NP".

From the wikipedia link: "Suppose that solutions to a problem can be verified quickly. Then, can the solutions themselves also be computed quickly?" If you can answer this question, you'll get a million dollars from the Clay Institute and a ton of accolades.

Some interesting problems which are not known to be in P or NP-complete are the integer factorization problem. Even still, if it turns out that P=NP, then we're going to have to retire RSA encryption.

(previously, and the fatal flaws in the proposed "proof")

posted by King Bee (19 comments total)

a million dollars from the Clay Institute

I've been saying for a while that the prize should be $1,166,666.67. If Perelman's turning down the million for Poincare, shouldn't the other six winners (should they eventually exist) share his money?
posted by madcaptenor at 9:23 AM on May 4, 2011

crivens, I grew up in Shaker. I know that building.
posted by oonh at 9:27 AM on May 4, 2011

If you can come up with an algorithm for solving Minesweeper, you've also solved the P vs. NP problem.
posted by jonp72 at 9:31 AM on May 4, 2011 [1 favorite]

I saw this on Slashdot earlier today and I was shocked at how many "what's P=NP and why should I care?" comments there were. I mean, I know it's Slashdot, but even from them I expected better. Sad.

Even still, if it turns out that P=NP, then we're going to have to retire RSA encryption.

Well, probably. But even then it could turn out that the actual solution is O(n^(2|||||||10)), where | is Knuth arrow notation. And the constant turns out to be Graham's number.

Realistically, I'd worry more about making sure you choose good factors for RSA, not to mention if/when quantum computing ever takes off.
posted by kmz at 9:36 AM on May 4, 2011

I thought factorization was already known to be NP-complete.

It is suspected to be outside of all three of the complexity classes P, NP-complete, and co-NP-complete. If it could be proved that it is in either NP-Complete or co-NP-Complete, that would imply NP = co-NP. That would be a very surprising result, and therefore integer factorization is widely suspected to be outside both of those classes

Harder than NP-complete?! Jeepers.
posted by DU at 9:37 AM on May 4, 2011

If you can come up with an algorithm for solving Minesweeper, you've also solved the P vs. NP problem.

Holy shit, P=NP!
posted by kmz at 9:38 AM on May 4, 2011 [1 favorite]

But even then it could turn out that the actual solution is O(n^(2|||||||10)), where | is Knuth arrow notation. And the constant turns out to be Graham's number.

Imagine me snorting water through my nose as I read this. Good one. =)
posted by King Bee at 9:42 AM on May 4, 2011

But even then it could turn out that the actual solution is O(n^(2|||||||10)), where | is Knuth arrow notation. And the constant turns out to be Graham's number.

Your exponent might be correct, but I don't think the case n=1 is going to be quite that difficult.
posted by Wolfdog at 10:06 AM on May 4, 2011 [1 favorite]

Factoring numbers of 1 digit isn't that hard anyway.
posted by DU at 10:08 AM on May 4, 2011

Oh wait...that's your joke. D'oh.
posted by DU at 10:08 AM on May 4, 2011

Humor is P-Space.
posted by Wolfdog at 10:10 AM on May 4, 2011

Well, wouldn't O(n^bignumber) be slower than trial division for any number you can write down? (If not, make bignumber bigger.)
posted by madcaptenor at 10:13 AM on May 4, 2011

In prepping me for a possible interview at Amazon, one programmer told me that they'd send in one of their more senior engineers to ask me increasingly difficult questions "until I broke". And that during this juncture they might throw me a P=NP problem. I said that if it car to that I would say I had solved it, just to piss the guy off.
posted by hellojed at 10:21 AM on May 4, 2011

Harder than NP-complete?! Jeepers.

Factoring is definitely in NP, because it's easy to verify an answer. So it's definitely not harder than NP-complete.
posted by Serf at 10:25 AM on May 4, 2011

I went to Case Western Reserve University, just down the road, and had an entire half a semester dedicated to P/NP. I had no idea it was born mere miles away though. Very cool.
posted by spamguy at 11:01 AM on May 4, 2011

Even still, if it turns out that P=NP, then we're going to have to retire RSA encryption.

No. First of all, no one has ever proven that prime factorization is outside of P to begin with. Second of all there are methods you can use to factor a prime number within a given probability bound that are in P time.

And third of all P time doesn't mean "fast". Algorithms can be in P time but still grow quickly enough to be useless for large inputs.
posted by delmoi at 11:39 AM on May 4, 2011

This is probably a good place to mention Impagliazzo's A Personal View of Average-Case Complexity (1995, linked file is PostScript). The paper goes one step further than just contemplating the consequences of P=NP or P!=NP by also considering how hard typical problems are. It lays out five possible scenarios, all the way from Algorithmica (P=NP), to Cryptomania (public key cryptography is possible, believed to be closest to reality).

It's an engaging read if you like this sort of thing.
posted by Serf at 12:01 PM on May 4, 2011

If you can come up with an algorithm for solving Minesweeper, you've also solved the P vs. NP problem.

1. Click really fast in a bunch of random places.
2. The map is probably now easy to solve.
3. If not, click some more.
4. If you hit a mine, no biggie! Just restart the game.
5. Now the game is easy to solve and you can click the remaining squares, no problem.
6. Epic win!

Where's my million bucks?
posted by Joe in Australia at 6:27 PM on May 4, 2011 [2 favorites]

Second of all there are methods you can use to factor a prime number within a given probability bound that are in P time.

Sure. Let P be a prime number. Then the factors of P are P and 1.
posted by Crabby Appleton at 8:18 PM on May 4, 2011 [2 favorites]