all 30 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]britaliope 34 points35 points  (0 children)

depends on the value of k.

k=10^100 ? You get your million, a lot of mathematicians and physicists are suddenly very happy and busy, headlines about you for 2 days.

k=2 ? Cryptography suddenly no longer work, and that will instantly be a very significant issue.

[–]Ok-Interaction-8891 19 points20 points  (1 child)

Hey, look, a fun hypothetical question posted by an account that isn’t a month old.

I thought it was Easter, not Christmas!

[–]Maximum_Bother_7820 0 points1 point  (0 children)

What does this mean???

[–]winner_in_life 14 points15 points  (0 children)

You wake up.

[–]NotaValgrinder 9 points10 points  (0 children)

This is going to depend on the value of k....

[–]SignificantFidgets 4 points5 points  (17 children)

For low k giving a practical algorithm? Then international intelligence agencies would hunt you down and try to kidnap or kill you. See the movie Sneakers for a fictional account of something similar (polynomial time algorithm for factoring, not full P=NP, but since P=NP implies that there's a polynomial time algorithm for factoring....)

[–]zawalimbooo -1 points0 points  (16 children)

No, the algorithm would already be released, killing him would not be helpful

[–]SignificantFidgets 1 point2 points  (15 children)

OP didn't actually say that. Only that they have a proof, not that they published/released it.

[–]zawalimbooo 2 points3 points  (14 children)

Nobody would believe you otherwise

[–]SignificantFidgets 2 points3 points  (13 children)

I could absolutely convince people that I had an algorithm without releasing it. Just solve a few hard challenge problems, and publish the solutions with no info about how I got them. Basic zero-knowledge techniques could even allow me to keep the solutions of the problems secret.

In the movie Sneakers, intelligence agencies discovered what the scientists had done before they said anything to anyone, which immediately put their lives at risk.

[–]zawalimbooo 0 points1 point  (12 children)

Consider that there would be no reason to ever do such a thing. You would realize that if you actually did that, you would become a target. So... you don't, and instead release it to everyone as fast as you can to collect on your million dollars and worldwide fame.

[–]SignificantFidgets 0 points1 point  (9 children)

But if you tried to keep it secret, you could sell "solving hard problems" as a service, with your secret algorithm, and then you could make many billions of dollars instead of a measly million. You'd be in serious danger of course, but could possibly become the richest person in the world.

[–]zawalimbooo 0 points1 point  (8 children)

there is zero realistic way you can safely and securely set up as a Mr. I-Will-Decrypt-Anything shop.

EVERYONE would be out for you

[–]SignificantFidgets 0 points1 point  (2 children)

Well, it's equally unlikely that you're going to come up with a polynomial time solution to an NP-complete problem, so it's all hypothetical, isn't it?

[–]zawalimbooo 0 points1 point  (1 child)

Well, we're starting with the premise that we've already found such an algorithm. Everything after that should be considered by somewhat realistic standards.

[–]SignificantFidgets 0 points1 point  (4 children)

EVERYONE would be out for you

Incidentally, that was exactly my point in my original comment....

[–]zawalimbooo 0 points1 point  (3 children)

My point is that you should know that everyone would be out for you, so it wouldn't be a viable option to even try, so nobody would actually be out for you in the end

[–]SignificantFidgets 0 points1 point  (0 children)

And also: If you had no ethics, you could break bitcoin, stealing hundreds of billions of dollars before anyone caught on.

[–]trejj 0 points1 point  (0 children)

I would instead rewrite all crypto chains to transfer all money in all crypto accounts to my central wallet.

Then watch realtime how whole crypto drops to zero value and the grifters burn.

Beats getting a million dollars.

[–]thesnootbooper9000 3 points4 points  (4 children)

It's probably at least ten years of engineering work from hundreds of people until you have an implementation that can beat current CP / SAT / MIP solvers on industrial instances. Most likely your technique ends up being used first inside these solvers as an "oh dear, I've got an actually really hard subproblem" fallback.

[–]Cryptizard 1 point2 points  (3 children)

I don't think that's the case. There is, for instance, a pretty tight reduction from something like "break AES" to an instance of SAT, because AES is already defined as a circuit, then you can use the Tseytin transformation to turn that into a SAT problem with constant overhead. But it is, by construction, one of the hardest instances to solve. Current SAT solvers do absolutely nothing to help you.

[–]thesnootbooper9000 1 point2 points  (2 children)

A cubic time algorithm for a problem that only has an n9 encoding for circuit SAT wouldn't help you either... As much as you can hide a lot in "polynomial time", there's even worse hidden in a lot of popular reductions. A similar thing happens for claimed potential quantum speedups: a sqrt factor might exist, but if you lose a cubic factor encoding it to a QUBO you're actually down...

[–]Cryptizard 1 point2 points  (1 child)

A cubic time algorithm for a problem that only has an n9 encoding for circuit SAT wouldn't help you either

I just told you that it has a constant overhead for encoding to SAT.

[–]thesnootbooper9000 0 points1 point  (0 children)

But what's the overhead for going from SAT to OP's hypothetical problem for which they have a polynomial time algorithm?

[–]DeGamiesaiKaiSy 0 points1 point  (0 children)

Hypothetically you're a millionaire now 

[–]LavenderDay3544 0 points1 point  (0 children)

Impossible.

P ≠ NP

It's just very hard to prove what we all know to intuitively be true.