Slashdot Mirror
Consequences of a Solution to NP Complete Problems?
m00nshyn3 asks: "If a person were to find a O(n) solution to an NP complete
problem, it would obviously be a great advance in computer science,
but what are the consequences of such a discovery? Would our most
popular implementations
of cryptography be useless overnight? It seems like there is a lot
of immediate damage that could occur if such a solution were found.
So if (when) the time comes, what is the responsible way for the
solution to be made public?" If you had such an algorithm in hand,
what could you do with it? It would be interesting to see how many
problems we could map into the NP Complete model.
Salesmen will certainly be happy when such an algorithm is found. For other classes of NP-complete problems, check this book.
Analogously, if it was learned that eating Hostess Twinkies that had been marinated in thai green curry sauce while bathing gave one super-strength and x-ray vision, we would have to become gravely concerned about the possible rise of Thai-Twinkie-powered super-criminals who know what we look like in our Underoos. This is clearly something that man was not meant to know. Won't someone think of the children?
Publish it as soon as possible, get credit for it, and rack up the monetary prize, don't you think?
-- The_Messenger
Considering that the Travelling Salesman Problem is NP complete and affects almost any problem that involves delivering something to several destinations in an optimal fashion. A solution to NP problems ould have widespread ramifications in improving many aspects of businesses that involve deliveries (including the airline business now that I think about it).
Is 42. ;)
-- Dan
I've actually got quite a few pizza this way. If this NP solution helps to speed up pizza delivery, I don't I would like that, at all.
Who gives a shit, cockgoblin? A problem in polynomial, n>=2, time is not solvable in linear time, which is what the original poster was claimimg.
Of course, you're an ignorant Slashdot fuck, so mathematical truth probably isn't important to you - and in fact is probably beyond the reach of your limited intellect.
Go back to playschool, fuckface - it's the only place people might look up to you, and that's only because you're taller.
...I'd break the news a lot like Linus did when he released 2.4.
"Oh, and by the way, here's the solution to some NP complete problem..."
Help us build a better map!
They can crack RSA crypto in O(n^123,312,352) The world is doomed!!!!
'polynomial time' can still be a long-ass time.
autopr0n is like, down and stuff.
"The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers."
- Bill Gates, _The Road Ahead_
Who gives a shit, cockgoblin? A problem in polynomial, n>=2, time is not solvable in linear time, which is what the original poster was claimimg.
Discussing cockgoblins and polynomial equations in the same post makes my day. Thanks for the smile.
Is "harvardian" from Harvard? What does he know anyways..
cpeterso
I've discovered a wonderful linear way to calculate optimal routing that I'd like to share, but unfortunately my keyboagu;[f=s af\sdfgsv asdfw352.,.f354asf
Prove that it's impossible to solve NP-Complete problems in linear time, before someone figures out how to do it.
dinner: it's what's for beer
Oh yeah? I've got a nifty little program right here that will factor your large primes in O(1)! Don't believe me? Read it and weep!
int factor(int largePrime)
{
return largePrime;
}
main(c,r){for(r=32;r;) printf(++c>31?c=!r--,"\n":c<r?" ":~c&r?" `":" #");}
I think I have this P=NP problem worked out. All you have to do is divide everything through by P. That way N = 1. Now where is my prize?
"I have a porkchop, you have a porkchop. I have a veal, you have a veal".
I dunno could be an interesting DoS attack :)
This must be Thursday, I never could get the hang of Thursdays.
Aggghhh. I thought that I'd escaped from talk of NP-Complete problems after my "machines and algorithms" final on tuesday. Is there nowhere I can hide?
Can anyone suggest a solution to this:
:) Which means I need to find a way to burn X bytes of warez onto N cds. where (N-1)*650MB = X = N*650MB, N a integer, and X is closer to N*650MB than (N-1)*650MB. Would this turn into an NP complete problem?
I have a lot of warez on my computer and running out of disk space. I need to burn those warez to 650mb CDs. But I want to use the space on those CDs efficiently, since I am too cheap to waste space like that
I solved it! I solved it!
I have the proof right here! I'm going to post it right now, right here on Slashdot!
Oh wait, there's a knock at my door. Hang in there folks, I'll be right back...
Muffled Yell
Thud
Long Silence
intellectual property law is philosophically incoherent. it is your moral duty to ignore it or sabotage it