Slashdot Mirror
No P = NP Proof After All
00_NOP writes "Internet commerce seems safe for now as Russian computer scientist Vladimir Romanov has conceded that his previously published solution to the '3 SAT' problem of boolean algebra does not work. If his solution did work it would have shown that many problems thought to be unsolvable with conventional computers — including decrypting your HTTPS encoded credit card number — would have been solvable in polynominal time. Romanov, who is very far from the sort of crank who normally claims to have proved P = NP or the opposite, is not giving up though..."
That's like the worst article ... ever. No information at all.
We should concentrate on figuring out whether God likes poutine.
Sounds like this guy needs needs some P.
OP || NP > - P
Now we get to wade through the "I can prove it when N=1" posts all over again.
Seriously? On Slashdot? People still value the pursuit of knowledge over here. I am sure your grandfather can understand that.
There are 5 related articles linked to the same article im sure you read that do exactly what you asked.
Since when does being a Socialist mean 'someone who has a different opinion than me'?
3 Sat is a kind of constraint satisfaction problem. Automated CSP solvers are clutch to micro-processor design and verification. Similarly, most logistics problems sit somewhere in NP-land, and everyone is happier when their mail gets to them a day earlier and a dollar cheaper.
Proof = No Proof
Yes, gimme the car analogy!
Solving this problem would save energy on the hundreds of thousands of NSA computers that are currently decrypting all of your e-mail and Skype conversations.
"I assumed blithely that there were no elves out there in the darkness"
It's the most important open question in computer science, and possibly mathematics.
Car analogy: P=NP - it's like everyone has always thought the supermarket was on the other side of the ocean, but it turns out that it's just a short drive down the street. The street may be flooded though.
Need proof that faster is better? Look at your computer. Now, Look at the computers of the 1960s. See?
All the stuff you do on a computer is the product of a collection of mathematical algorithms and instructions called programs.
One way to make programs faster is to make the algorithms faster... Remember, "faster is better", Grandpa? Grandpa?
(He's asleep, I'll just tiptoe out...)
Because, if prove that NP=P, all NP problem would be solvable in polynomial time, including problems like, the traveling salesmen: http://en.wikipedia.org/wiki/List_of_NP-complete_problems
Seriously. If people want to prove or disprove a theory, let them be... it doesn't have to be pejorative. The sciences require the ability to explore (even in areas deemed 'pseudo science') to truly test the answer space and find the global minimum.
Well, we then can solve all sorts of scientific problems quite a bit faster. For example, suppose your grandfather has a brain aneurysm. Say a doctor wanted to make a 3D model of your grandpa's brain from CT and MRI scan's so that he could explore it, see where the aneurysm is, and then practice surgery on the 3D brain model so that he knew exactly how to do the surgery on your grandfather and avoid cutting on critical parts of his brain. This would increase the likelihood your grandpa would survive the surgery, and also probably reduce chances of complications since the surgeon would know exactly where the aneurysm is and will have already practiced the surgery. Currently, building accurate 3D models is very slow from 2D picture "slices" of CT / MRI scans. If P=NP, then there exists a way that it can be sped up significantly, maybe saving hours to days of time and allowing the doctor to do his work faster thus also increasing the chance your grandfather will not have complications. Sure, it may also mean it can enable someone to steal his credit card number, but there is research into biometric security that P=NP will help out as well by making it faster to do. Biometric security means having ATM machines that would recognize your face, fingerprints, voice or a picture of your iris and identify you uniquely without having to put in any silly numbers.
That brings me to an interesting point, / . is just "the ramblings of socially-inept, technology-literate news-mongers".
Basically works like this...
Encryption works by performing a calculation that is easy to perform one way, but very difficult to perform in reverse. It's more than just a subjective "easy" and "very difficult" though -- there are ways to measure how hard a problem is to solve. Encryption works because we're pretty sure of this distinction between "easy" and "very hard".
If P = NP, then we were wrong, and there really wasn't a distinction. This means all encryption is now broken, because it is just as easy to decrypt messages as it is to encrypt them.
However, most people believe P != NP. But we haven't proved it yet, mathematically, so people are always a little nervous about the topic.
You can think of P as "easy problems", and NP as "hard problems". If P = NP, then easy = hard, and encryption is broken. If P != NP, then encryption is safe.
This. How is GP even a real question? Could we have given your 89yo grand father a "sincere 'down-to-earth' answer" to the "what is quantum theory" question? Oh, he did not understand? Never mind quantum cryptography, then. Never mind research into prime factorisation.
Seriously, what is with people thinking "if I can not understand it fuck it" these days? How arrogant have we become?
In your requested layman's terms:
Proving that P=NP would prove that mathematically "hard" problems can be solved "easily." Encryption algorithms are designed around the fact that these hard problems can't be solved quickly by a computer. If P=NP, all modern encryption fails, which means most Internet commerce comes grinding to a halt until another solution can be found.
All NP-complete problems (the "hard" problems mentioned above) derived from the 3-SAT problem, so if 3-SAT were proven to be easily solvable (3-SAT is in P), all NP-complete problems are easily solvable.
This is just one real world application of this problem.
Basically the idea of P=NP is summed up in this question: For any problem where it is easy and quick to verify if a potential solution is correct or not, is it also possible to find the solution in the same timeframe?
In compsci anywhere you have to brute force something, right now the answer is "No" but if it turns out to be true it would have the potential to make crypto useless (since crypto relies on N being a very large number, large enough to where it's not worth it to spend NP time breaking the encryption, but where P allows for realtime encryption/decryption.
I read a car example somewhere, probably slashdot. OK so if you have misplaced your car keys, this is a P!=NP problem. It's easy to confirm whether or not you have found your keys at any point in the search, but finding the keys themselves likely will require looking through all possible locations where they could be.
A possible P=NP variant would be if you had a buzzer attached to the keys triggered to make noise when you clap, then you just clap and walk to the buzzing. No wasted effort searching, P=NP (or at least, as close as you can get).
What I first read in the equation was: To Park is Not to Park
Nae king! Nae laird! Nae yurrupiean pressedent! We willna be fooled again!
Being able to solve NP-Complete or NP-hard problems optimally in polynomial time would allow engineers to produce better/smaller (on the circuit level) computer systems faster, as the field of physical design automation and testing is littered with NP-complete (or NP-hard) problems. It would also leave a lot of engineering researchers free to look into something else.
"I've spent my whole life figuring out crazy ways to do things. It'll work." -- Montgomery Scott, "Relics"
"unsolvable with conventional computers"
They're not unsolvable, they're infeasible. There's an important difference.
You can solve TSP for 1 million cities if you're willing to wait a few billion years, but the fact that you're waiting a few billion years makes it infeasible.
They might instead working on solving the problem of finding usable algorithms to decrypt email and skype conversations.
:).
Just because you know a solution exists doesn't mean you know all the steps to solve it
Either
N=1
or
P=0
Actually, he's very much the classic style of crank. Instead of giving us a formal proof, his proof is a proof by example consisting of a great deal of code that has to be scrutinized by hand for conceptual errors. It works fine on his test cases of course; so therefore to him his "proof" is "correct."
> How does the solving of problems like these really help the world? I would like a sincere 'down-to-earth' answer that my 89 year old grandfather can understand and therefore be in position to donate to the effort of solving such problems.
Here's one for your grandfather then. When you bank online, you go onto a secure web site. The information you send to your bank is digitally encrypted. A bunch of mathematicians have demonstrated that the 3SAT problem is just as hard, or harder, as breaking the encryption that keeps your grandfather's bank info secure. So, if Romanov turned out to be right somehow, it wouldn't be safe for your granddad to bank using computers anymore, because Romanov would have indirectly created an algorithm that could be used to crack the encryption in a reasonable amount of time.
Other Slashdotters will come up with plenty of other examples why 3SAT is important.
Well, this proof could lead to more complex math being solved sooner rather than later.
Bad from a security standpoint, but great for other areas of research, such as medical research.
Things such as protein folding could be done more efficiently, which could lead to better understanding of why some things fail and create potential cures or vaccines to target these failings.
It would change quite a few things if found to be true.
If false, however, we might need to rely on quantum computers for such computing power, if we can get a big and stable enough one built.
Two examples are given: decrypting encoded Internet traffice and decrypting encoded credit cards. If this problem is solvable by conventional computer, I see two major side-effects. First, it would mean we would have to be a lot more worried about the safety of our private information. since cracking current encryption would be a matter of short time. Second, it could mean a significant reduction in the funding and research for "unconventional" computer, the most prominent example being quantum computers.
Assuming your 89-year-old grandfather isn't a tech junkie, what this means to him is his credit card might not be as safe as it used to be. And even if he doesn't do online banking, I'd be willing to bet his bank trades his money with other banks using encrypted electronic transfers.
There are tons of problems which are NP hard. So if we solve one, solving these problems will be feasible.
Timetabling - Making timetables automatically.
Resource Distribution - (Similar to timetabling) - which can sort out how limited resources should be utilised for maximum efficiency
Bin Packing - Which will make compression algorithms and sorting your favourite stuff into optical disks more efficient
TSP - Which can get the optimal route between a number of locations - the shipping/transport industry will love this
Protein Folding - Is also NP hard, which means that the biochemical and medical industry gets a significant boost
(etc)...
It'll also totally ruin cryptography.
How does the solving of problems like these really help the world?
Because solving this problem can help solve another problem that impacts the world more than the original problem.
So, it has been proved that it is not possible to prove something we may or may not be able to prove?
Not to bust anyone's bubble, but the factoring problem is actually not known to be NP completely and evidence points to the fact that it is no, since if it could be shown to be then this would prove that NP=Co-NP. Similarly, the discrete logarithm problem is also not known to be NP-complete. Therefore, public key cryptosystems should be fine.
Symmetric key cryptosystems such as 3-DES and AES should also be fine. They aren't known to be NP complete problems, and in fact there are no theoretical guarantees about their security at all. They just seem to create messages that are difficult to decrypt given our current cryptoanalytic abilities. In fact, there are NO known NP-complete crypto schemes around today.
TL;DR - No encryption schemes will be broken if it is proved that P=NP.
his errors are obvious really, anyone with a college degree who browses his would could have caught them easily.
Are you taking lessons from BadAnalogyGuy?
Life is a great ride, the vehicle doesn't matter
I think we can safely assume the GP's grandpa probably doesn't know what being "solvable in polynomial time" means. In fact, I think we can safely assume he has a grade 8 or 9 education.
Is this the same Russian Romanov that nuked Chicago and had that dreadnought fleet in that historical Red Alert 2? If so, I'm calling in Tanya.
A 3-sentence comment in a blog is converted into a 4-sentence blog post by someone else, and that is converted into a news story by Slashdot?
AES-256 is known to be in complexity class P, in fact it's in complexity class C, problems that can be solved in constant time. The idea that problems solvable in polynomial time are easy and those that aren't are hard is not true for problems of practical size. See http://world.std.com/~reinhold/p=np.txt
One of the funniest comments ever!
that's too smart!
You're one of THEM!
It pays to be obvious, especially if you have a reputation for being subtle.
On the same blog, actually:
http://cartesianproduct.wordpress.com/2010/12/29/what-if-p-np/
morcego
I'm sorry... When in the history of human existance has more people been pulled up from poverty than the past decade?
China, India, the many smaller countries in Asia, the burgeoning middle class in Africa... You see only what is 3 feet in front of you, ignoring everything else.
- These characters were randomly selected.
Really? I guess if you ask stupid questions you get stupid answers.
I'm going to break a cardinal rule of slashdot here...
Are you a mathematician?
Finally had enough. Come see us over at https://soylentnews.org/
I would be most grateful if you gave an example of that 'other problem' that impacts the world which could be solved. From your missive, I am assuming that the problem actually exists.
Thanks.
Seriously, what is with people thinking "if I can not understand it fuck it" these days? How arrogant have we become?
1 word: Reagan. He's the one who started all this nonsense about how it's a bad thing to be educated and intelligent. It made his hick supporters "feel bad" so now they lash out at the "intelligencia".
Not bad for a troll.
Anti-intellectualism in American Life, by Richard Hofstadter published in ... 1963. Not 1988. In fact Hofstadter was dead by '70.
"‘the more learned and witty you bee, the more fit to act for Satan will you bee" John Cotton 1642 in Boston USA
Its across the political spectrum, not just a republican thing.
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
Yes, but the supermarket is in Venice.
Twenda Learning: Educational Apps that Engage.
You ignored the P=0 solution, by assuming it wasn't in your third step..
How is a quad-processor DOS computer on steroids any better than a powersaving 16-core ARM mobile CPU+GPU which you can carry around in the palm of your hand?
No realy...
Here be signatures
"so grandpa. it's like this. if you lose your cell phone, it's P-easy to say it's not on the counter, or in the couch. but it's NP-hard to say where they are if you don't remember. what we're trying to figure out is whether we left the phone on, so that we can just dial it up and walk towards the ringing. if it is, then NP-hard is P-easy. if we left it off, then NP-hard means we gotta look everywhere in the house."
slashdot: where everyone yells sarcastic metaphors to themselves to understand the issue
(since crypto relies on N being a very large number, large enough to where it's not worth it to spend NP time breaking the encryption, but where P allows for realtime encryption/decryption.)
If by "N" you mean the "N" in "NP", then I think you've got it wrong. The N is not a number, it stands for "non-deterministic", meaning that problems in NP can by solved by non-deterministic turing machine (which we don't know how to build) in polynomial time (the "P" stands for polynomial). Problems in P can be solved in polynomial time by a regular (deterministic) turing machine.
There are many problems that are too hard for humans to solve. We may be able to give a good guess at the answer, but to answer them correctly we must use a computer. The development of the computer and the research that has determined how to solve problems on a computer has brought about lots of good things. We can analyze medical images for cancer, launch satellites into space, fly around the world, and talk to anyone we want whenever we want. However, there is yet another set of problems that too hard even for computers to solve. Much like us, computers may be able to give a good guess at the answer, but they cannot answer them correctly. Research into P=NP is there to let us determine the nature of these problems. If P=NP, it means our computers can solve these problems, even if not on today's machines. If P!=NP, it means that our computers (of today) won't ever really be able to solve the problems. In either case, the decision will have enormous impacts on how our governments and corporations invest in research in the future.
Though it should be noted that polynomial time doesn't nessacerally mean practical time.
note: i'm known as plugwash most places but i screwd up registering that here somehow in the past and now can't register
I have a question on this. Assuming an algorithm was found for the 3-SAT problem, in polynomial time, and therefore proves that P=NP, how does that actually get us any closer to an actual algorithm for factoring large numbers in polynomial time, which is would be a completely different algorithm. I realize that we might know that such an algorithm is possible, but how does knowing something is possible make the problem any easier to solve? For now, we aren't sure that it's impossible, so we might as well assume it's possible, and therefor try to solve the problem. But the people working on these problem pretty much assume it's possible. So to repeat the question. How is knowing P=NP any different from assuming P=NP when you're trying to find an algorithm for solving these really hard problems? Can all NP problems can be solved with the same algorithm, or a variation thereof?
Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
You think wealth is not defined by economic strength, but by its 1st derivative, the economic growth?
P and NP are both sets.
Faster execution means:
1. Less polution of the earth ("Hah, carbondioxide is bullshit!" - yeah say that to Venus, lol)
2. Giving America ("Fsck yeah! Here to save the motherfscking day, yeah!") the upperhand in decoding terrorist communication so people's lifes can be saved.
This all is ofcourse not realy entirely true, but at least you can lie with a straight face and not feel completely guilty about it :)
Here be signatures
1 word: Reagan. He's the one who started all this nonsense
Ignorant people believe they're knowledgeable. With this comment, I fear you've revealed that you're in that category.
I read a car example somewhere, probably slashdot. OK so if you have misplaced your car keys, this is a P!=NP problem. It's easy to confirm whether or not you have found your keys at any point in the search, but finding the keys themselves likely will require looking through all possible locations where they could be.
Terrible example because your "NP" example is inherently a polynomial time problem, so you've got it exactly backwards. Doesn't matter how many dimensions your universe has, if it takes one time unit to search one unit cell, then inherently the total time required to search any given region can only increase as a polynomial as the region scales linearly. So searching for car keys is very strictly a polynomial time problem and scales somewhere between power of 2 and power of 3.
Want a NP problem for an old person, whip out ye olden times interstate road atlas (or if the interstate is too modern for them, try railroad timetable). Ask them to find the fastest route to visit all their friends and relatives and note how the effort required is pretty easy at low digits and gets terrifyingly difficult once you have a couple hundred, to the point where whim or guess -n- check is the best solution. Now thats something that does not scale polynomially.
One widely held, and completely wrong, belief about P != NP is that if a poly solution exists for currently non-poly problems, it'll be a simple click of a mouse to instantly solve all poly problems, which is pretty ignorant. What if the poly time solution has a constant C factor that is a multiple of the age of the universe? Or if the "easy" squared coefficient numerically equals a mere google to the power of a google to the power of a google? Its very interesting mathematically, and as the answer to a trivia contest type question, but it does not necessarily have to have any real world impact at all.
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
All supermarkets are on the other side of the ocean if you go the wrong way.
Citation please?
I think a better way to put it is this....
Many security systems, like those used to protect online banking, online commerce in general etc, are based on these problems being very hard to solve. If it turns out that they are not as hard as we think, then we are not as safe as we think we are.... If we don't have honest people looking for the solution and letting everyone else know, then, we will not found out whether we are safe or not until someone dishonest figures it out and uses it against us.
Just putting it in the first terms, that is, the terms of what we lose if it turns out to not be true, puts it in terms of the status quo vs discovering the vulnerability. Obviously, its better that we continue as we are, and nobody finds the vulnerability ever... because that means what we are doing works, and there is no need to change. However, it ignores the long term risk of the discovery happening later by someone else.
Overall, if anyone goes on to prove P=NP, then I want it to be someone like this guy who just wants the recognition, rather than someone who just wants the money.
"I opened my eyes, and everything went dark again"
That's what I was going for, yes, glad I achieved that lofty goal :)
Always listen to experts. They'll tell you what can't be done and why. Then do it. -- Robert Heinlein
Those who say it can't be done are usually interrupted by others doing it. -- James Arthur Baldwin
Do you even lift?
These aren't the 'roids you're looking for.
Let's isolate the N.
N = P/P
if p == 0 then fail
'The tyrant will always find pretext for his tyranny.' - Aesop's Fables
Last I checked, I didn't see your name on the list of those entitled to know the secrets of the universe.
Yes. Anything but profit that doubles every quarter, forever, is a catastrophic failure.
ASCII stupid question, get a stupid ANSI
Actually, to build a cryptosystem off an NP-complete problem would be a very bad idea indeed.
It is worth observing that while NP problems are believed to be hard in general, most of the `average' instances
can be solved quite easily. There are several papers (Levin84 was the first, but see also
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.8775 ) on the topic.
A further remark: people seem to assume that "NP complete" means "as hard as conceivable". This is utterly
false. A solution to an NP problem can, by definition, be verified by a Turing machine in polynomial time; this
is not the case for more general classes of problems (for example those in class PR or R).
No way, if he had - the analogy would have been more entertaining.
What happened to BadAnalogyGuy anyway, he seems to be posting as a mere mortal these days - with no bad analogies.
It's like watching a bald eagle take a crap.
"Lame" - Galaxar
This. How is GP even a real question? Could we have given your 89yo grand father a "sincere 'down-to-earth' answer" to the "what is quantum theory" question? Oh, he did not understand? Never mind quantum cryptography, then. Never mind research into prime factorisation.
Seriously, what is with people thinking "if I can not understand it fuck it" these days? How arrogant have we become?
There's a whole profession dedicated to decoding things like this and summarizing them into easy to understand tidbits we call "NEWS ARTICLES". There are probably very few people who understand the science being done at CERN yet a large number of average joes have some idea what is being researched there due to this mysterious "NEWS ARTICLE" phenomenon. Hey, I think I'll go check out one of these "NEWS ARTICLE" websites.. perhaps slashdot.org. You may want to rethink things if you think the person you replied to is the person who's being arrogant in this discussion.
Getting the citations for the GP is an NP-complete problem...
And he's saying things that make absolutely sense to me, so I'll skip on the citations.
- These characters were randomly selected.
Then what is "P=NP", and why is it relevant?
That is the question.
This is just wrong. Both prime factorization and discrete log, have polynomial size certificates and are therefore in NP. While none of the problems are know to be NP complete (and as you say, we suspect they are not). Proving that P=NP will still show that there exists polynomial time solutions to both problems.
Agreed, but I had to think of something to say and that's the only field I know enough about to comment. Im sure there are better examples. It basically reduces something that requires ~ base^N computations or higher to only requiring ~ N^power computations. That's like reducing hours to seconds for sufficiently large N.
That brings me to an interesting point, / . is just "the ramblings of socially-inept, technology-literate news-mongers".
My computer IS from the 1960s, you insensitive clod!
Dark Reflection
No he didn't. He left out the 5th & 6th steps, which are:
5) ???
6) Profit!
P=NP is involved in the route-finding your GPS does. Calculating the shortest and/or fastest route between two locations is a hard problem, On a long journey there are a huge number of possible routes that could be taken and only one shortest route and one fastest route. Currently the GPS does approximations to find these, solving P=NP could result in faster and more accurate GPS routefinding. What good is that? Well consider a 1% improvement in routing to a road haulage company, that 1% off wear and tear plus fuel. It costs at least ~$170000/year to run a truck, so say half that is insurance and pay, so thats $850/year per vehicle simply by using a better algorithm... now roll that out over the whole fleet.
It means that you can solve something that would take you hours in seconds. Maybe even something that would take you days in seconds.
That brings me to an interesting point, / . is just "the ramblings of socially-inept, technology-literate news-mongers".
coNP = NP would be surprising for a couple of reasons, some of which fundamentally more groundbreaking than the graph isomorphism problem. specifically, it would collapse he polynomial time hierarchy to level 1. The implications of this are beyond huge; coNP problems are just \Pi_1, but this would prove \Pi_n = \Sigma_n = NP for ANY n >= 1 (coNP is child's play in that respect).
Prime factorization is in NP (proof is just about as trivial as they come) and therefore if P=NP, there must exist a polynomial time algorithm for prime factorization. Who gives a fuck if factorization is NP complete or not, that doesn't matter in the slightest. I suggest you learn what NP complete means, as a start.
ASCII stupid question, get a stupid ANSI
They are outside of P but are not actually hard for NP. Therefore proving P=NP is not useful in solving these problems.
Seriously? This got 4: Informative on Slashdot?
The graph isomorphism problems of course IS in NP, it's just not known to be NP-complete. The same goes for discrete log/factoring. Having a polynomial algorithm for an NP-complete problem would yield a polynomial algorithm for all three of these problems.
source: http://stackoverflow.com/questions/311064/are-there-public-key-cryptography-algorithms-that-are-provably-np-hard-to-defeat
Apples to apples. How does that handheld compare to the same-sized handheld of the 1960s?
You're arguing the wrong way. Factoring and other problems related to crypto aren't believed to be NP-complete, but they are known to be in NP. Thus, a proof that P equals NP implies that integers can be factored in polynomial time, which would allow to break cryptosystems efficiently. (cf. http://en.wikipedia.org/wiki/P_%3D_NP#Consequences_of_proof)
Who modded this informative? Bah!
You say some things which are correct. Factoring is not known to be NP-complete. If factoring were NP-complete, that would prove that NP=co-NP, which would be very surprising. Discrete logarithm is not known to be NP-complete. Those things are correct.
You say some things which are incorrect. Graph isomorphism is known to be in NP. It's completely trivial to show that graph isomorphism is in NP. What's not clear is whether it's in P (which is what this whole P=NP thing is about). Discrete logarithm is also known to be in NP, and that's also trivial to show.
While there are no known crypto systems which rely on NP-completeness, every crypto system relies on something which is at least as weak as NP-completeness. More precisely, every crypto system in current use relies on something which is in NP. If P=NP, then every crypto system in current use is broken.
Computers can solve simple problems immediately. Difficult problems take a bit longer. If we could simplify difficult problems, computers could solve them immediately. One type of difficult problem which has a possibility to be simplified is the NP type.
The possibility is so small that he may be better to donate to a humanitarian cause. The humanitarian cause may help someone survive that can answer this question. Even if they can't, he at least helped them survive.
Aside from the obvious "What handheld?"-question; powersaving, shaders and RISC?
Here be signatures
Being NP-Complete or not is irrelevant here. All of your examples are in (or can be stated as) NP. If P=NP then all of them must have a poly time algorithm that solves them. Even if the actual algorithm is not known it puts a serious downer on their use as crypto primitives: most "billion times the life of the universe" estimates are based on the assumption that our existing exponential algorithms are close to as good as possible. If this is no longer true the estimates could be way off.
The NP-Complete part matters if there is a P != NP proof. In that case NP-complete problems are proven to be "really difficult" as they are then shown to be not in P. Still all your examples would be as they are today. We think that they are difficult, but have not yet proved that they are not in the P part of NP (the set... not the name!)
Interesting, because the news articles I come across in the paper that "my 89 yo grand father" reads are typically not about university grade mathematical problems. They are featured on news sources like, hey I see you mentioned one; "slashdot", was it? Where people who are actually interested in this kind of matter and usually have a scientific background that helps greatly in actually understanding it, roam.
Not to say I did not probably misjudge the intent of GP; I re-read his post after replying and had some afterthoughts as well. My knee-jerk reaction was not just based on his post, though; it is far too often that I see it become acceptable to openly refer to seemingly hard science as "useless". To the point that scientific institutions are now money wasting unless proven useful, instead of the other way around. We see it in budget cuts and this lack of foresight and insight greatly disturbs me; have we forsaken our scientific heritage and are we ingrateful to the tangible products of centuries of mathematics and other science?
If his question was out of pure curiosity, then my reply was not to him (I would proceed to wonder why he then asks people to explain it to his granddad and not just to.. himself?). If, however, he is voicing the creeping condescence to science as a respectable institution of our society, then please allow me to be the first to say: fuck all y'all.
What about this:
http://en.wikipedia.org/wiki/Fast_Syndrome_Based_Hash
Unlike most other cryptographic hash functions in use today, FSB can to a certain extent be proven to be secure. More exactly, it can be proven that breaking FSB is at least as difficult as solving a certain NP-complete problem known as Regular Syndrome Decoding.
Yeah I know it is just a hash...
No encryption schemes will be broken if it is proved that P=NP
Huh? The decision version of factoring is in NP, so if P=NP we can factor numbers in polynomial time.
TL;DR - No encryption schemes will be broken if it is proved that P=NP.
Also there is no guarantee that a P=NP solution must be feasible. There may exist a polynomial solution to cracking AES, BUT that specific problem may result in polynomial coefficients that are so unimaginably large as to require lots of Knuths uparrow notation to express numerically, making it a meaningless victory.
Sample dialogue: "The good news is its poly, in fact not only poly, but linear, in fact not only linear but coefficient of one, so if we double the key length then we only double the search time. The bad news is we're talking about doubling a trillion times the lifetime of the universe assuming every atom in the universe did an op every Planck time. Other than that, no problemo, because P = NP."
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
So does non = one? Maybe if n = e!
NP problems aren't "hard," rather they are "easy to check." The class of NP problems are problems which can be checked in polynomial time. Problems in "P" can be solved in polynomial time. Roughly, P=NP would be very surprising because it means that we've been wrong every time we thought it was easier to verify a solution to a problem than it was to come up with the solution.
Every story under Slashdot lately has some asshole griping about the inadequacy of the story subject.
Hey, adequacy police assholes: don't take it so fucking seriously. And stop taking yourselves so fucking seriously. This is a place to hang out and discuss random topics of nerd interest. That's it. That's all this place is. We're not compiling the text to Bible 2.0. Yet you attack the adequacy of story subjects as if you were some sort of religious fundamentalist and we were insulting your religion.
Get the fuck over yourselves.
intellectual property law is philosophically incoherent. it is your moral duty to ignore it or sabotage it
Just because something is solvable in polynomial time does not mean it's solvable quickly. For example, the best solution could be n^123471239481872349 time. This would be infeasible for all n>=2.
I'm glad that Vlad hasn't given up.
Would somebody with half a clue PLEASE mod this post down???
It's just mis-information of the worst kind -- to lay people (even for CS grads that didn't take any computational complexity courses) it sounds right except that it isn't.
Where are my fucking mod points.....
Don't quote me on this.
That is wrong.
N = NP
is a idea, which means
N is a something, perhaps a formula, a treasure map, the password to a computer.
NP is what you get for N.
In if you find N, you can with calculation find NP.
N is a NP to some other thing again, because of correlation.
2*4 is still related to 2+2, because it is 2+2+2+2, etc.
If we figure out this, it means we can get from A to D without going from A, we do not need to go anywhere either.
Solving N = NP means is more or less figuring out how to aquire omnipotence.
I find it to be a really silly idea.
You are correct that factoring, graph isomorphism and the like are not known to be NP-complete but they certainly are in NP. Hence a polynomial time algorithm for any NP-complete problem would povide a polynomial time algorithm for the problems you listed as well.
You misunderstand. Having a polynomial time algorithm for factorization does not prove P=NP, but proving P=NP means there's a polynomial time algorithm for factorization.
This proves that P!=NP right there. Go get your $1M!
Whoosh!
Factoring and discrete logarithm are in NP, but not known to be NP-complete. That means they are definitely polynomial time if P = NP, and might be broken even without showing P = NP.
If you have a computer, and the only way in is via logging in.
Lets say it has a 10 digit unicode password.
How do you figure out what the correct password is without bruteforcing it? Providing nothing silly like to much feedback(half the reason WEP was cracked), the only feedback you can get is True or false(true meaning access to the computer).
How do you then find the password without guessing it?
If we solved N == NP, then we have omnipotence.
If P == NP, any puzzle where you can ask if you've got the right answer and get a yes/no quickly can be solved quickly, too, and if there's a "best" solution, it can also be found quickly (through binary search).
Now imagine the puzzle is "find the most efficient antenna", or "find the most aerodynamic car frame that has enough space inside", or "find the shortest description of this stock market data", and you start to get at the power of the thing. Forget public key decryption -- a large swathe of engineering (and logistics) problems can be solved by just asking for a solution. Theorem proving can be automated, even.
(For pedantics: yes, I know "polytime" does not necessarily correspond to "quickly" -- but now try to find an n^1000 algorithm in the wild. Also, "shortest description of this stock market data" may be PSPACE since the decompression algorithm could run forever, but I assume you'd want to get the answer reasonably soon.)
Dumbass. Try McCarthy. But McCarthy was so stupid even he couldn't have invented anti-intellectualism all by himself.
Fascism trolls keeping me up every night. When I starts a preachin', he HITS ME WITH HIS REICH!
Not a stupid question. In fact, you would have been justified asking this question back when Galois was doing his work on abstract algebra in the 1830s. Or when Fourier was doing his work on temperature a bit earlier than that.
Over a century later, the work of both Fourier and Galois has moved so far from the abstract and so deeply entrenched in the practical, consumer-applied engineering fields that it would be hard to name anything in technology that didn't at least consider the application of both.
Fourier analysis is now used in all sorts of detection and classification schemes. Its principles are applied to video and audio compression as JPEG and MP3. Galois' finite fields are the basis for a myriad of digital coding schemes for error detection and correction -- not the least of which is the venerable Reed-Solomon code used in compact discs (CD).
There may not be an immediate application for such abstract theory (finite fields in 1830???), but the advancement of knowledge plants seeds from which we reap the fruit for centuries.
http://en.wikipedia.org/wiki/P_versus_NP_problem
This is the 21st century. No longer is information on trades controlled by corresponding guilds. You obviously have an internet connection, use it moron.
Infinity divided on infinity is still theoretically speaking 1.
And again: What number is a variable that has no size or value?
mod parent up, original poster doesn't have a clue
Polynomial time vs. Non-polynomial time? That's what I thought it meant. Ok. So its Quick solvability vs. Quick checkability and if P=NP its both.
That brings me to an interesting point, / . is just "the ramblings of socially-inept, technology-literate news-mongers".
The 3-SAT problem really is a problem saying "given this circuit of boolean gates, determine if there are any inputs you can set to make the final output gate signal TRUE". So consider you want to make a computer that implements the factor guessing game: you give it a composite number and a possible factor, and it shows a light if the factor you input is a factor of the composite number. It's possible to build that kind of computer because it's easy to check if the factor divides the composite: just divide and see if you get a remainder.
But now consider that the special purpose computer you built is really just a bunch of boolean gates. The program is fixed, so it can be modeled as a lot of gates, too. So you write down a description of this machine, where the input gates correspond to the composite and factor, and the final output gate is TRUE if the light would go on, otherwise FALSE. Then you fix the composite so they're no longer inputs - e.g. if you want the composite to be 3, you force the two first input gates high.
Now you have reduced factoring this number to finding input gate values so that the output gate returns TRUE... and that's what 3-SAT does. You dump the whole thing through the solver and it tells you which input gates you need to set; then you divide the composite by the number those gates represent, readjust the set of gates, and repeat.
The only good thing about Reagan is, he proved deficits don't matter.
You're missing the point: if P=NP, then any problem that is in NP (e.g., prime factorization) is also obviously in P (since, well, NP=P), and so, solvable in polynomial time. In fact, if P=NP, there is no "hard for NP", since it's all really P.
Maybe you're confusing it with the converse: if P!=NP, then, sure, it doesn't follow that it's hard to solve (for instance) prime factorization -- it might be in P, in NP-complete or neither.
Sorry but your logic is the wrong way around there.
If someone proves that 3SAT (an NPC problem) is in P then this means P=NP. That is, everything currently known to be in NP is in P. Factoring is known to be in NP (easy proof, just guess the factors of a number) and hence P=NP would prove that factoring is in P.
However you are correct that factoring is not known to be NPC. So it is possible that we could prove factoring to be in P and that does not imply P=NP.
Not to bust anyone's bubble, but the factoring problem is actually not known to be NP completely and evidence points to the fact that it is no, since if it could be shown to be then this would prove that NP=Co-NP. Similarly, the discrete logarithm problem is also not known to be NP-complete. Therefore, public key cryptosystems should be fine.
TL;DR - No encryption schemes will be broken if it is proved that P=NP.
You got that wrong. If P=NP, then NP=Co-NP, so your public key cryptosystems are broken. (Also, if P=NP, all problems in P are NP complete)
Wrong. If P=NP, all problems in NP (including NP complete and Co-NP problems) are solveable in polynomial time.
This increases your quality of life much the same way little improvements in blacksmithing increased farmer's quality of life in the middle ages. His hoe doesn't chip as easily on a rock in his field.
Also, it's hard to come up with a sincere "down to earth" answer for why DOING SCIENTIFIC RESEARCH helps the world. It's just too difficult to not be sarcastic.
Republicans like Reagan and Palin and Beck are the flag-bearers for anti-intellectualism in our times.
Mod this up, and mod GP -1, plain wrong.
Who gives a fuck if factorization is NP complete or not, that doesn't matter in the slightest.
Nitpick: If P=NP, then factorisation, or any other problem in NP, is NP complete.
One down-mod won't help. You have to compare the up-mod rate with the down-mod rate. There are more lay people for whom it sounds right than people with half a clue. This process converges to +5, end of story.
Hate to burst YOUR bubble, but you appear to have the meaning of "NP-complete" backwards. Proving P=NP doesn't simply mean that all NP-complete problems are now in P. It means that ALL problems in NP (including, but not only, the subset NP-complete) are now in P. Now if you're claiming that decryption is not in NP, I think Mr. Turing might have a bone to pick with you.
So RSA, 3DES, and AES not being in NP-complete doesn't matter whatsoever... If P=NP then they're all in P.
no, it means that you can solve CERTAIN things in an amount of time comparable to the amount of time it takes to verify the solutions as being correct. the "Big Question" is whether or not the class of problems thought to be hard to solve but easy to verify, could have an unknown shortcut to solve them as easily as verifying a putative solution as being correct.
in cryptographic terms this would mean cracking encryption or forging a signature in a comparable number of operations (within a few orders of magnitude or so, and not scaling fast with bit count) as it takes to decrypt with the key or check that the signature is valid.
this does not translate to "solving problems faster" but to "solving CERTAIN problems faster"
Snowden and Manning are heroes.
Your grandfather is likely aware of the role that encryption played in WWII, so use that. You say something like this:
After WWII, encryption became entirely dependent upon math to prove that, even with computers, some encryption schemes would be virtually impossible to break in any reasonable timeframe. In other words, as long as the math was safe, the encryption was safe.
Proving P = NP means that the math isn't safe anymore. It used to be safe because, given the state of mathematical knowledge at the time, no one knew how to program a computer to break the encryption. But now, they know that it's possible, in theory, to program a computer to break any current encryption scheme, so all the encryption that we use--government communications, secure commerce, military communications--is vulnerable.
On the bright side, this means other things that seemed to be mathematically impossible are possible, like using computers to simulate biological processes to explore potential cures and disease mechanisms.
Anyone who loves or hates any language, platform, or manufacturer, doesn't know what they're talking about.
just what i need, truck drivers going past my house because their P=NP GPS will save them 37 milliseconds by doing that
Snowden and Manning are heroes.
If boot times were the only criterion, computing peaked in the 80s. Sigh... I do miss the C64 sometimes.
Actually, general computing on the C64 was usually just as fast as it is today. It wasn't until you tried to do number crunching (e.g., generate a Mandelbrot image) that you missed speed.
You couldn't do multimedia either. However, with a SID-like, dedicated chip approach to multimedia, the 2 MHz would be just fine. I haven't used it myself; but I understand there is video editing done with a C-64 based system, presumeably using some kind of cart or other add-on.
Does not the existence of rainbow tables to resolve hashes indicate that in some unconventional manner that P = NP?
And even if he doesn't do online banking, I'd be willing to bet his bank trades his money with other banks using encrypted electronic transfers.
My grampa keeps his money under his mattress, you insensitive clod!
Every time a notion of P=NP or P!=NP comes up on slashdot, about 30 or 40 people say the same thing... to be frank, it's getting tiring.
This might be a solution (and not the only one, even) if the notion of P = NP actually described a situation where P and N are supposed to be constants (and that the right hand side multiplied them together), and that the expression P = NP were actually intended to convey a notion of algebraic equivalence.
However, it is neither.
When discussing P's equivalence to NP, both P and NP are actually (implied) functions of another variable, not variables themselves, and the notion of them being equal only means that the function which describes the asymptote of either function as the variable approaches infinity is equal to a constant multiple of the function which describes the asymptote of the other function. For polynomials, this asymptote is simply the term in the function with the largest degree.
Oh, and "P" stands for polynomial. N stands for non-deterministic.
File under 'M' for 'Manic ranting'
"This would be a surprising result since it would prove that the graph isomorphism problem is in NP."
Do you mean it would prove that graph isomorphism is in co-NP? Graph isomorphism is fairly easily shown to be in NP: the isomorphism is the witness.
Of course I also got the P NEQ NP one just in case...
--
Marc A. Lepage
Software Developer
"There's a whole profession dedicated to decoding things like this and summarizing them into easy to understand tidbits we call "NEWS ARTICLES"."
And if you read one of these news articles that happens to be about something you already know about, it turns out that instead of taking the time to understand and summarise them, most journalists just write any old crap that's usually not only wrong but demonstrative of their complete lack of effort to understand the source material.
It's been proven that all NP problems are actually the same problem. That is, it is possible to transform any NP problem into any other NP problem in polynomial time. So, if you come up with an algorithm that can solve the 3-SAT problem in poly time, it is relatively easy to come up with a polynomial time algorithm to turn the traveling salesman problem into a 3-SAT problem.
Fair enough. My old CS professor called NP "non-polynomial" time so NP=P meaning something like being able to reduced 2^N computations to N^power computations. I read about it again after your post it says something like P = "speedy solvability" and NP = "speedy checkability". With your encryption example I understand. So its like private/public key, easy to verify but takes forever to actually factor. It seems to me to be somewhat semantic, as NP implies it takes longer to solve than P if you were to actually brute force it. For the record, I am not a CS guy.
That brings me to an interesting point, / . is just "the ramblings of socially-inept, technology-literate news-mongers".
Oh that's alright, we'll just make a machine that includes the AES cracking algorithm as a machine instruction. Then the time complexity of cracking n bits of AES is only 2n+1 clock cycles!
Republicans like Reagan and Palin and Beck are the flag-bearers for anti-intellectualism in our times.
I'm not disagreeing that they are a tiny little itty bitty subset of the flag bearers, but they seem kinda outnumbered and outgunned by the sports-fans, jocks, sportscasters, religious preachers, Christian creationism activists, intelligent design authors, romance novel writers, tv newsreaders, pretty much the entire pop culture industry from hip hop musicians to movie actors, the entire freaking population of California Lousiana and Mississippi, and american idol viewers.
After all, wasn't Little Wayne and Eminem hard core right wingers? Oh wait...
But other than them folks, us slashdotters are like a brilliant beacon of light on the American Renaissance, yeah.
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
Not to burst your bubble, but you're utterly confusing NP and NP-complete. Problems in NP-complete are harder than problems in NP but not in NP-complete. But let's take this slowly ...
First off, graph isomorphism is in NP (you state it isn't). If you give me a table of the node mapping then I can verify the isomorphism in P time. Graph isomorphism is not known to be in NP-complete, but this is of no practical importance as we shall see below.
The discrete logarithm problem is also in NP. Any practical encryption scheme can be reversed in NP since any practical encryption scheme goes forwards in P. These problems are / are not known to be NP-complete (delete as applicable; I don't care enough to look it up), but this is of no practical importance as we shall see below.
In summary: a problem can be in NP without being NP-complete! Now, here's the crux of the matter:
Any problem in NP can be transformed into a problem in NP-complete in polynomial time by definition of NP-complete.
Therefore, a polynomial algorithm for any NP-complete problem is automatically a polynomial algorithm for any problem in NP.
This includes discrete log, graph isomorphism, etc. etc.
A proof that N=NP is likely to (but does not necessarily) provide such an algorithm. This proof that P=NP does in fact provide such an algorithm (except it's broken, but still ...)
So yes, all encryption schemes will be broken if it proved constructively that P=NP.
What you are saying is incorrect. Although it is true that the factoring problem is not known to be NP-Complete, the decision version of it IS known to be in NP (along with the graph isomorphism problem). Furthermore, there exist polynomial time reductions from every problem in NP to every NP-Complete problem. Therefore, if there were a polynomial time algorithm for an NP-Complete problem, it could be used to perform integer factorization efficiently.
Particularly if you count the number of people pulled out of absolute poverty. That is defined as:
David Gordon's paper, "Indicators of Poverty & Hunger", for the United Nations, further defines absolute poverty as the absence of any two of the following eight basic needs:
While the US and Europe may struggle at the moment, we have not fallen this far. I don't mean to take away from the hardships that many endure right now, but the number of people living without the most basic of needs has been going way, way down. Today we estimate that 1.7 out of 6.9 billion live in absolute poverty, it's still a huge number but 5.2 billion do not.
There's also relative poverty but I care less about that, sure some other guys may make 10x as much as you but as long as you have all the basic needs covered you're not suffering in nearly the same way.
Live today, because you never know what tomorrow brings
RSA and 3DES / AES are completely different kinds of thing. Your mathematics is good but your crypto is not.
RSA would not automatically fold if P=NP. It would depend on the constant factor k. Suppose that the outcome of P=NP includes a new factoring algorithm which runs in polynomial time. For a size N RSA key, this algorithm takes O(N^2) time... But the new algorithm requires 18 million years setup time on our most powerful computer. This is a perfectly good polynomial time algorithm, the mathematicians will be satisfied, but RSA remains untouched.
3DES and AES don't rely on a trapdoor function at all. They're believed to be hard, but not any particular kind of hard. A P=NP breakthough is as likely to cause problems for AES as it is to cause the collapse of the automotive industry or a huge boost in attendance figures at aquariums.
Factoring and discrete logarithm may not be NP-complete, but they are in NP. If P=NP, they would be broken.
Factoring is in NP, thus if you can factor in P (when P = NP) then encryption schemes do break. A problem doesn't have to be NP-complete to be affected by this.
Well NP Hard isn't Hard for NP, but at least as hard as the hardest NP problem. It could exists outside NP. I'm going to admit to not following all the yelling above, but I wanted to point that out. As for citations.
http://en.wikipedia.org/wiki/NP-hard
Some NP-Complete problems are NP-hard. It is possible for NP=P to be true and NP-Hard problems to still not be solvable.
Momento Mori
I hear this a lot. Are there any NP problems that are usually hard to solve?
Play Command HQ online
Who gives a fuck if factorization is NP complete or not, that doesn't matter in the slightest.
I might be wrong here but wouldn't a proof that P!=NP only guarantee that NP-complete problems are not in P? That is, if factorization is not NP-complete, then it might actually be in P regardless of whether P=NP or not. So yes, if P=NP it is all moot, but if P!=NP we would much prefer encryption that's NP-complete to break (or provably not in P).
One strange thing is that nobody seems to know of any useful polynomial algorithms where the exponent is very large. There are lots of n^2 algorithms, some n^3 ones. What about n^1000, or even n^6? Are we just too dumb to recognize these problems, or do they not exist?
I don't think that contradicts your point anyways, since sure P != NP in the first place.
make a few potholes and slow them by 57 ms an they will go another way :->
I weep for humanity.
Hey buddy, can i bum a karma? ~}CinderellaManson{~
It's absolutely not theoretical. It's possible that the denominator is larger than the numerator (or vice versa), hence infinity divided by infinity would not equal to 1. Infinity divided by infinity is indeterminate.
Examples that disprove your claim:
lim x->infinity ( x/ln(x) ) = infinity
lim x->infinity ( ln(x)/x ) = 0
P=NP when N=1. There I solved it, where's my $1 million?
It's not so clear. Also posted somewhere in this thread this text [http://world.std.com/~reinhold/p=np.txt] might help you understand the matter.
Last night it was quite clear that NP is P.
OK, I'll take a sincere stab at this one.
Suppose you're an export company making a shipment, and you're renting ten shipping containers. Could you get by with only eight? Solving that three dimensional jigsaw puzzle is hard, but it's easy to *see* that you've got a good solution once you've come up with it. Such problems whose solutions are easy to verify (regardless of whether they are easy to arrive at) are called "NP". That stands for "Non-deterministic polynomial", but for now all you need to know is "NP" means "easy to check".
Of course some problems are easy to check solutions because the solutions themselves are easy to arrive at. If you were shipping crushed ore, you'd take the total volume of ore and divide it by eight to see if it would fit in eight containers. If I were to check your answer I'd do the same thing you did to arrive at the answer, because the solution is *simple*. Such easy to *solve* problems are called "P" for "Polynomial". All "P" problems are automatically "NP" -- they're easy to check, because all you have to do is repeat the solution.
When you're messing around with an NP problem, like our container packing problem, it's natural to ask whether there's an easy way to get the answer. Sometimes there is a surprisingly easy answer. One example is when you punch in an address to your little GPS and it spits out the best route to take. Seemingly that's a very hard problem but it turns out to be a "P" problem. As we struggle with our very difficult container packing problem, maybe we just haven't been clever enough yet to find the easy solution. Then it would be a "P" (easy to solve) problem.
The P=NP problem amounts to this: do all easy to verify problems have easy to calculate solutions that we can look for?
On the face of it, this seems like a silly question to ask. Most (but not all) problems we deal with in day to day life are of the "easy to check" variety, but that doesn't make them easy to solve. It's hard to come up with that 10% budget reduction the boss asked for, but easy to tell if you succeeded. It's easy to tell if you bought your girlfriend the right birthday present, but that doesn't make choosing the present easy. We certainly don't assume that easy to verify equals easy to solve in our day to day lives, so what makes anyone think that P might equal NP?
Well, it turns out that there are certain problems whose solutions can easily be transformed into a solution to *any* NP (easy to verify) problem. That means if we had an easy solution to any of these problems, we'd have an easy solution to *all* problems where the solution was easy to verify. Another way of saying this is if any of these "NP Complete" problems are "P", then all NP (easy to verify) problems are "P" (easy to solve). That seems too good to be true. It's as if getting that 10% reduction in budget your boss wants somehow told you the right present to buy your girlfriend. Of course you can't boil a problem like how your girlfriend feels about you down to pure numbers, but you *can* boil down something like how many containers you need to pack your shipment down to numbers. "P=NP" means that there is an easy way to do that.
Most of us are not so optimistic as to believe P=NP, but *we can't be sure*. Some of the NP-Complete problems seem tantalizingly simple. For example, let's say you and I are choosing up teams for a game. We don't know the players, somebody has helpfully pinned a rating of 1-100 on each of them. Ensuring that we have the most equally matched teams is an NP-Complete problem. If we could do that easily, we could magically solve the container packing problem easily too.
Everyone knows how to choose up sides, right? The captains alternate picks. We're so used to doing that we just assume that is the fairest way to divide up players, but experience shows that one team often ends up much stronger than the other when teams are picked this way. This method is guaranteed to not pick the worst possible division, but little more. Suppose the p
Post may contain irony: discontinue use if experiencing mood swings, nausea or elevated blood pressure.
I'm not sure why you got modded troll.
Here's a simple answer: if p = np, curing cancer gets done in short order afterward. If p != np, we can focus our cancer curing energies on other strategies.
If you want to understand why that's the case, it requires significantly more in-depth knowledge of both computer science and current efforts at curing cancer.
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
I just wish we could have meept back. He put BadAnalogyGuy to shame.
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
The integer factorization problem *can be no more difficult* than NP. Put differently integer factorization is NP-easy. It is trivial to show that integer factorization can be no more difficult than NP (and is in fact in NP), as multiplication can be performed in polytime (giving a polynomial time verifier) and brute force operates in exponential time on the digit length of the input (thus providing an exponentially bounded solving algorithm). HOWEVER, it has NOT been proven that integer factorization is NP-complete (yes, GP did misspeak, saying "NP completely"). Put differently, there is no generalized polytime conversion from an NP complete problem (such as TSP) to integer factorization. Thus, per current understanding, it would be ENTIRELY POSSIBLE to prove that integer factorization is in, say, P, and even with a constructive proof, not have given a polytime algorithm for TSP and friends. Thus the GP is incorrect, a proof that P=NP *WILL* break RSA/DSA and friends, but a break of RSA/DSA & co is not a proof that P=NP. This is why the question of NP-completeness is important. Independently of all this, though, I'd hazard that any constructive proof that integer factorization is (not) in P would likely be a proof that P(!)=NP, as the (seemingly) most likely alternate proof would be a proof that NP-complete(!)=co-NP-complete, which as far as I can tell is less analyzed. NOTE: Strong possibility that the last statement given above is bullshit as IANAC[omplexity]T[heorist] but IAAC[omputer]S[cientist] and I know several complexity theorists.
Except you're wrong too. NP-complete is a set of NP problems not known to be in P but can be verified in P. If P=NP, all problems in P are not and never were in NP-complete.
I am officially gone from
I think saying "too hard" is misleading -- computers solve problems that are too time-consuming for humans to solve on their own. Anything a computer can calculate, humans can calculate (if the species lives long enough).
Thank you. This was great. Reminds me why I love slashdot.
He's saying that there are other ways to perform public-key encryption without using NP-complete problems, so we could work around P=NP, if that were the case.
Also, it does matter that integer factorization (not "prime factorization"; where did you get that term?) is not known to be NP-complete - since it's just known to be NP-hard, it might or might not be discovered to be feasible if P=NP. Or it might be harder.
3-SAT is in NP, so it's solvable by definition in polynomial time – on a non-deterministic turing machine. It's whether it's solvable in polynomial time specifically on a deterministic turing machine that defines whether it's in P.
If X is between 1 and 200, is X divided on X still 1? :P
Besides, infinity is not a number nor a size, but a concept.
A/A=1, yes?
And I might still be learning lim at the moment, so I do not understand the evidence you bring against it either.
Yes, but that's beside the point. Factorization and discrete log are in NP (well, technically, their decision problems are, anyway).
The point is: if P=NP, then everything in NP is equally hard. So, it's useless to talk about the hardness of factorization compared to something else in NP.
No. If you solve one problem it doesn't mean you have proven that all such problems are soluble.
OK, then replace the quad-processor DOS computer on steroids with a quad-processor MacOS computer on steroids. :-)
The Tao of math: The numbers you can count are not the real numbers.
P and NP are both sets.
In that case, the problem hinges on whether or not the N subset of NP is empty...
Actually I might be wrong about that.
But either way using rainbow tables to resolve hashes doesn't indicate this.
You ignored the P=0 solution, by assuming it wasn't in your third step..
There may have been a reason for that... Let's see:
N = P/P where P = 0
Substitute Zero for P...
N = 0/0
N =
ERROR: Divide by Zero exception at line 2.
Ah, you see, that form of math is frowned upon in computer science...
You can solve TSP for 1 million cities if you're willing to wait a few billion years,
The TSP is quite solvable. There are pathological cases that are NP-hard, but most cases aren't. The classic Bell Labs stochastic solution for the TSP (break path into 3 sections at random, reassemble in shortest way, repeat until no improvement for a while) will converge on the shortest path most of the time, and a near-shortest path almost all the time. This approach requires something like O(N log N) time.
There are many hard problems like that. Linear programming has the same property. It's unknown whether factoring has that property.
In the very unlikely event that NP=P, what people "believe" in doesn't mean much. A proof that NP=P is groundbreaking enough to invalidate almost everybody's "beliefs" in the field of computational complexity.
Besides, I don't think the encryption algorithms are "believed" to be "harder" than NPC problems. Nobody has the faintest idea whether there'll be a 18billion year setup time, or a O(N^10000) for the "harder" problems in P if NP=P. The discussion of what really follows if NP=P is pretty moot actually.
Don't quote me on this.
If P=NP, all modern encryption fails
If P=NP, most commonly used public-key encryption fails. Many symmetric key encryption algorithms remain safe (including one-time pads).
rage, rage against the dying of the light
Your definition is the definition of NP, not NP complete. NP is the set of all problems that are in NP and NP hard (i.e. all problems in NP can be reduced in polynomial time to a problem in NP-complete). If P=NP, all problems in NP can be reduced in polynomial time to any other problem in NP (because they can be solved in polynomial time)
Oversimplifying what P=NP would mean for dummies:
1) you have a problem known to be slow to solve(in NP)
2) you create a description of your problem as a sequence of logical operations (if you can make a logical circuit for it this can be done)
3) you translate that description in a special formulation known as CNF using just 3 variables(this point was already proven as possible and fast for all NP problems)
4) ??? - you take your newly developed polynomial time 3 SAT CNF solving algorithm and use it to compute a solution to the problem stated at 1)
5) $$$ - you now have a polynomial time algorithm to solve the problem stated at 1)
Glossary:
P - Polynomial time = Fast to solve even for very large inputs (finding if a given number is even)
NPC - Non determinisctic polynomial time complete = Very very slow to solve for somewhat large inputs (finding a solution for the travelling salesman problem with lots of cities)
NP - Non deterministic polynomial time = Contains all problems that are in P in addition to many others that aren't in P.
CNF - Conjunctive normal form = A way to write boolean algebra expressions(sequences of logical operations)
SAT - Satisfiability = Find out if there are any values for the variables that make a boolean expression true
P.S. for those still reading:
As for prime factorization it is known that it is in NP and in Co-NP but AFAIK there exists no proof as to whether it is in NPC, co-NPC or P. But we also know it to be in FNP and we know that if P=NP then FP=FNP and vice versa, hence prime factorization would be solvable in polynomial time by a turing machine as all FP problems are.
Bibliography:
See your favourite boolean algebra/logics book for CNF and SAT and your favourite computation theory book for Complexity.
My old CS professor called NP "non-polynomial" time so NP=P meaning something like being able to reduced 2^N computations to N^power computation.
Wow, your CS prof messed up big time in explaining that. The question whether NP is polynomial or not is one of the biggest freaking open questions in CS.
The whole "speedy solution" vs. "speedy check" way of describing P vs. NP is not the one I prefer, because it is a bit derivative. The root of the NP class comes from a concept in automata theory called a Nondeterministic Turing Machine. The simple explanation of this is that it's a mathematical model of an infinitely parallel computer, in the sense that it can perform any finite number of computations in parallel (there's no upper bound on the number of threads, and these threads are truly parallel).
NP is the class of problems that such a computer could solve in polynomial time. Since such a computer can spawn a separate thread for each candidate answer, the alternative statement of this is that it's the problems for which proposed solutions can be checked in deterministic polynomial time—since the generic nondeterministic algorithm for solving any problem is "try all candidate solutions in parallel, and pick one that checks out."
In other words: if P=NP, that means that there is a relatively efficient single-threaded simulation of an infinitely parallel computer.
Are you adequate?
I am trying to explain the importance of P(=|!=)NP to the GP's 89 year old grandfather. Simplicity is probably valued over a pedantic explanation.
The status of graph isomorphism is maybe unclear. Well, it is unclear whether it is in P, in NP-complete or in between. But it trivially is in NP. Since encoding the bijection can be done in polynomial space.
provided the problem is in NP I can reduce is to any NP-complete problem (for instance SAT) in polynomial time. Solving that instance of SAT in polynomial time (if P=NP) will provide a solution for the graph isomorphism instance. All these step can be performed in polynomial time.
So YES, showing a polynomial algorithm for SAT or 3-SAT WILL have an impact on security.
The N is not a number, it stands for "non-deterministic", meaning that problems in NP can by solved by non-deterministic turing machine (which we don't know how to build) in polynomial time (the "P" stands for polynomial). Problems in P can be solved in polynomial time by a regular (deterministic) turing machine.
And the simpler way of explaining this (not guaranteed to be 100% accurate) is the following: a non-deterministic Turing Machine is basically an infinitely parallel computer, in the sense that it can spawn any finite number of truly parallel threads at no cost. An NP problem is one that you can solve in polynomial time in such an infinitely parallel machine; the general nondeterministic algorithm is just to spawn one thread for each candidate solution, have each thread simply check whether the candidate passes, and return a successful try.
If P=NP, what that means is that there is an efficient single-threaded simulation of an infinitely parallel computer.
Are you adequate?
Agreed, but I had to think of something to say and that's the only field I know enough about to comment. Im sure there are better examples. It basically reduces something that requires ~ base^N computations or higher to only requiring ~ N^power computations. That's like reducing hours to seconds for sufficiently large N.
It might mean reducing hours to seconds. But it also might mean reducing millions of years to mere centuries.
The Tao of math: The numbers you can count are not the real numbers.
Polynomial time vs. Non-polynomial time? That's what I thought it meant. Ok. So its Quick solvability vs. Quick checkability and if P=NP its both.
P means polynomial time; more exactly, it is the set of all problems which can be solved in polynomial time by a (deterministic) Turing machine. But NP doesn't mean non-polynomial time. It means nondeterministic polynomial. The set of NP-problems is the set of problems which can be solved with a non-deterministic Turing machine in polynomial time. Especially all P problems are also NP problems. However the reverse is only true if P=NP.
The Tao of math: The numbers you can count are not the real numbers.
Here's a vim command to correct your message: :%s/.*//g
Graph isomorphism and prime factorization are in NP (obviously).
Well, as long as you don't break an ordinal rule ...
The Tao of math: The numbers you can count are not the real numbers.
did you learn hacking in computer science III? with that kind of understanding, I don't think you could hack windows 6, much less windows 7.
Well, O(n^1000) algorithms are not exactly what I'd call useful.
If you can solve it in one Planck time for some problem size, solving it for twice that size will need about 10^240 times the age of the universe.
The Tao of math: The numbers you can count are not the real numbers.
Not totally. The one-time pad will remain secure.
The Tao of math: The numbers you can count are not the real numbers.
That's why i said you assumed it wasn't, that step isn't valid if P=0 (it's the usual flaw in those 1=0 "proofs").
That form of math is frowned upon in mathematics.
You just got here, how do you know what it's for?
You don't need experience to get to that result. Simple logic tells you that the one starting will inevitably get the stronger team. The argument is easy: First, group the players in pairs: The first pair contains of the two best players, the second pair gets the next best player, and so on. Now it's obvious that in the first round, the two people of the first pair are chosen. The captain who gets the first choice of course will pick the better one. But the captain who has the first choice will also have the first choice on the second pair, and on each following pair. Therefore he will inevitably get the better team.
It's also easy to give a strategy which is more fair: Instead of the commonly chosen pattern ABABABAB..., let them choose according to the pattern ABBAABBA... That way, while A gets the first pick on the first pair, B gets the first pick on the second pair, and so on. Or if you group the players in four, captain A will get the best and the least good from each group of four, while captain B will get the middle two.
Of course it still isn't guaranteed to give the optimal teams, but it at least doesn't guarantee captain A the better team. IN your example, captain A would get the total score 88+12+6+1 = 107, and captain B would get the total score 50+25+3+1 = 79. So in this case captain A would still get the much better team, but at least not as pronounced as with the ABAB... method. And if we take instead e.g. the scores 85, 83, 81, 70, 52, 44, 32, 15, then the usual ABAB... method would give the total scores 250/212, but the ABBA... method would give 222/240, so in this case B would get the better team, but his advantage would not be as pronounced as the advantage A has with the usual ABAB... method.
The Tao of math: The numbers you can count are not the real numbers.
N = 1
How does the solving of problems like these really help the world?
A solution to this particular problem would launch us directly into a Star Trek-like universe of easily broken encryption, universal language translators, and inductive learning systems so easy to create that grade school children could create AI. That's week one. Week two would be the wholesale destruction of economies worldwide as all these newly smart systems show us how inefficient everything we do really is. Week three is the last great war as billions of people revolt against the rule of the machines and those who control them. You'll want to have left Earth by then.
Depends. It might be that the best algorithm for breaking our public key cryptosystems is O(n^1000). That's polynomial, but still safe.
The Tao of math: The numbers you can count are not the real numbers.
This proves that P!=NP right there. Go get your $1M!
Wow, you get 1 million factorial dollars for that? :-)
The Tao of math: The numbers you can count are not the real numbers.
You have it exactly wrong on your definitions, according to wikipedia, and certainly according to my theory prof back when I was studying this stuff regularly.
I am officially gone from
Not to bust anyone's bubble, but the factoring problem is actually not known to be NP completely and evidence points to the fact that it is no[t]
Not to burst your bubble, but while factoring isn't believed to be NP-complete, it is definitely in NP. This means that it is actually easier to solve than NP-complete problems.
More evidence that factoring is not NP-complete is that there exists an algorithm called general number field sieve that has sub-exponential running time. If factoring were NP-complete, it would mean that all NP-complete algorithms could be solved in sub-exponential time, which is considered unlikely. Factoring is probably easier than NP-complete problems.
In fact, it seems that the current public-key algorithms are all apparently easier to solve than NP-complete problems.
"Screw Sun, cross-platform will never work. Let's move on and steal the Java language." - Visual J++ Product Manager
There are only 112 boolean variables required to break 3DES and between 128 and 256 variables to break AES (depending on key size). To find one factor of a 1024 bit integer would require at least 512 boolean variables. Any P solution of 3SAT would be O(F1(variables) + F2(statements)), and while I don't know how many individual statements 3DES, AES, or factoring would require at those bit-lengths I assume the number of independent variables would probably dominate the time and space requirements.
Kennedy faced a similar problem in the early 1960s, as I heard recently on an NPR story about the Peace Corps. An early proponent had proposed it to some big philanthropy organization, but the representative shook his head and said "American youth aren't that idealistic." But Kennedy didn't believe that, and managed to draw out some inner altruistic quality of American youth that many thought didn't exist.
http://www.peacecorps.gov/index.cfm?shell=about.history.speech
Of course it will, but then how do you transfer one-time pads on the internet? We're back to the problems people had before asynchronous crypt was invented.
asymmetric*.
Sorry
Your definition is the definition of NP, not NP complete. NP-complete is the set of all problems that are in NP and NP hard (i.e. all problems in NP can be reduced in polynomial time to a problem in NP-complete). If P=NP, all problems in NP can be reduced in polynomial time to any other problem in NP (because they can be solved in polynomial time)
FTFY
Here's the mistake which I addressed
You're treating infinity as a number such as 1 or 200. If you divide 200 by 200, of course it's 1. Your range of x (1 to 200) is not infinity. Doing mathematical operations on infinity has its own set of rules (i.e. infinity times infinity is infinity, but not dividing them), since infinity is not a real/normal number.
If A is a real number, excluding 0. But since there are variables out there that range from the negative numbers to positive numbers (charge, for instance, may be -1 C, 0 C, or +1 C), you can see where the problem may lay.
Two functions, x-e (changed for clarity) and ln x are both infinity if you let x be infinity. If x is a number that's roughly 4.1386519464791 (irrational number), then x-e /(ln x) = 1 (or nearly 1). But if x is infinity, then x-e /(ln x) is indeterminate because x-e gets larger faster than ln x in the long run. That's why you have to take the limit, to see what happens when x approaches infinity (and you have to perform L'Hospital's Rule).
Try infinity/infinity on a graphing calculator and see what you get, or visit Wolfram Alpha.
No you don't. If it were a factorial symbol there would be a period after it to end the sentence. There is no period after it so it must be an exclamation mark.