# No P = NP Proof After All

#### CmdrTaco posted more than 3 years ago | from the big-o-my-god dept.

318
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..."*

## Wow. (0, Offtopic)

## Anonymous Coward | more than 3 years ago | (#35337592)

## Re:Wow. (0)

## burtosis (1124179) | more than 3 years ago | (#35337616)

## Re:Wow. (0)

## Anonymous Coward | more than 3 years ago | (#35337786)

Beats the summary, then, which is just plain wrong.

## Re:Wow. (0)

## Anonymous Coward | more than 3 years ago | (#35338068)

P = NP iff P == 0 or N == 1.

I think you can see where I'm going with this!!!!

Michael Crawford

## Well.. DUH (-1, Offtopic)

## Anonymous Coward | more than 3 years ago | (#35337600)

Everyone knows that Poo =/= No Poo.

Either it's covered with poo or it's devoid of poo.

## An easier question (0, Offtopic)

## Schiphol (1168667) | more than 3 years ago | (#35337624)

## Re:An easier question (-1)

## Anonymous Coward | more than 3 years ago | (#35337838)

I know /.ers hate discoursing in stereotypes, but are all Russian men brilliant chess players and mathematicians and all Russian women gorgeous [askmen.com] femme fatales [gawker.com]?

## Let me ask a "stupid" question (-1, Troll)

## bogaboga (793279) | more than 3 years ago | (#35337640)

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.

Thanks.

## Re:Let me ask a "stupid" question (3, Insightful)

## Schiphol (1168667) | more than 3 years ago | (#35337666)

## Re:Let me ask a "stupid" question (1, Insightful)

## Anonymous Coward | more than 3 years ago | (#35337760)

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?

## Re:Let me ask a "stupid" question (-1)

## Anonymous Coward | more than 3 years ago | (#35337810)

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".

## Re:Let me ask a "stupid" question (1)

## Canazza (1428553) | more than 3 years ago | (#35337946)

that's too smart!

You're one of THEM!

## Re:Let me ask a "stupid" question (0)

## Anonymous Coward | more than 3 years ago | (#35337970)

Really? I guess if you ask stupid questions you get stupid answers.

## Re:Let me ask a "stupid" question (2, Interesting)

## vlm (69642) | more than 3 years ago | (#35338008)

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.

## Re:Let me ask a "stupid" question (0)

## Anonymous Coward | more than 3 years ago | (#35338136)

1 word: Reagan. He's the one who started all this nonsenseIgnorant people believe they're knowledgeable. With this comment, I fear you've revealed that you're in that category.

## Re:Let me ask a "stupid" question (4, Informative)

## kelemvor4 (1980226) | more than 3 years ago | (#35338266)

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.

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.

## Re:Let me ask a "stupid" question (1)

## 228e2 (934443) | more than 3 years ago | (#35337670)

## Re:Let me ask a "stupid" question (1)

## Anonymous Coward | more than 3 years ago | (#35337674)

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.

## Re:Let me ask a "stupid" question (1)

## Anonymous Coward | more than 3 years ago | (#35337682)

Yes, gimme the car analogy!

## Re:Let me ask a "stupid" question (1)

## Errol backfiring (1280012) | more than 3 years ago | (#35337792)

## Re:Let me ask a "stupid" question (3, Funny)

## benjamindees (441808) | more than 3 years ago | (#35337684)

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.

## Re:Let me ask a "stupid" question (0)

## Anonymous Coward | more than 3 years ago | (#35337820)

Just because you know a solution exists doesn't mean you know all the steps to solve it

## Re:Let me ask a "stupid" question (0)

## Anonymous Coward | more than 3 years ago | (#35337694)

It's the most important open question in computer science, and possibly mathematics.

## Re:Let me ask a "stupid" question (2)

## MadKeithV (102058) | more than 3 years ago | (#35337706)

## Re:Let me ask a "stupid" question (2)

## Bucc5062 (856482) | more than 3 years ago | (#35337900)

Are you taking lessons from BadAnalogyGuy?

## Re:Let me ask a "stupid" question (1)

## MadKeithV (102058) | more than 3 years ago | (#35338184)

## Re:Let me ask a "stupid" question (1)

## Crudely_Indecent (739699) | more than 3 years ago | (#35338256)

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.

## Re:Let me ask a "stupid" question (1)

## Chuckles08 (1277062) | more than 3 years ago | (#35338012)

## Re:Let me ask a "stupid" question (0)

## Anonymous Coward | more than 3 years ago | (#35338168)

All supermarkets are on the other side of the ocean if you go the wrong way.

## Re:Let me ask a "stupid" question (4, Insightful)

## VortexCortex (1117377) | more than 3 years ago | (#35337716)

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...)

## Re:Let me ask a "stupid" question (-1, Troll)

## Dunbal (464142) | more than 3 years ago | (#35337822)

Look at computers in the 1960's. Look at economic growth in the 1960's. Look at computers today. Look at economic growth today. See? It's not as clear cut as you would like to it be. Especially when you don't define "better". Faster computers are FASTER. Period.

## Re:Let me ask a "stupid" question (3, Insightful)

## Rakshasa Taisab (244699) | more than 3 years ago | (#35337962)

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.

## Re:Let me ask a "stupid" question (1)

## Zorpheus (857617) | more than 3 years ago | (#35338098)

## Re:Let me ask a "stupid" question (1, Funny)

## canajin56 (660655) | more than 3 years ago | (#35338240)

## Re:Let me ask a "stupid" question (1)

## V!NCENT (1105021) | more than 3 years ago | (#35338046)

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...

## Re:Let me ask a "stupid" question (1)

## OakDragon (885217) | more than 3 years ago | (#35338296)

## Re:Let me ask a "stupid" question (0)

## Anonymous Coward | more than 3 years ago | (#35337718)

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

## Re:Let me ask a "stupid" question (0)

## Anonymous Coward | more than 3 years ago | (#35337906)

## Re:Let me ask a "stupid" question (1)

## V!NCENT (1105021) | more than 3 years ago | (#35338126)

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 :)

## Re:Let me ask a "stupid" question (1)

## petermgreen (876956) | more than 3 years ago | (#35338086)

Though it should be noted that polynomial time doesn't nessacerally mean practical time.

## Re:Let me ask a "stupid" question (1)

## Antisyzygy (1495469) | more than 3 years ago | (#35337732)

## Re:Let me ask a "stupid" question (1)

## larry bagina (561269) | more than 3 years ago | (#35338206)

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

## Re:Let me ask a "stupid" question (1)

## Antisyzygy (1495469) | more than 3 years ago | (#35338290)

## Re:Let me ask a "stupid" question (1)

## del_diablo (1747634) | more than 3 years ago | (#35338286)

Then what is "P=NP", and why is it relevant?

That is the question.

## Re:Let me ask a "stupid" question (2, Informative)

## Anonymous Coward | more than 3 years ago | (#35337754)

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.

## Re:Let me ask a "stupid" question (2)

## n4f (1473103) | more than 3 years ago | (#35337780)

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.

## Re:Let me ask a "stupid" question (1)

## L4t3r4lu5 (1216702) | more than 3 years ago | (#35337994)

Are you a mathematician? [tvtropes.org]

## Re:Let me ask a "stupid" question (5, Insightful)

## The MAZZTer (911996) | more than 3 years ago | (#35337782)

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).

## Re:Let me ask a "stupid" question (1)

## digitalsushi (137809) | more than 3 years ago | (#35338048)

"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."

## Re:Let me ask a "stupid" question (3, Informative)

## NdrU42 (1420507) | more than 3 years ago | (#35338062)

(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-deterministicturing 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.## Re:Let me ask a "stupid" question (3, Insightful)

## vlm (69642) | more than 3 years ago | (#35338158)

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.

## Re:Let me ask a "stupid" question (1)

## Lord of Hyphens (975895) | more than 3 years ago | (#35337796)

## Re:Let me ask a "stupid" question (0)

## Anonymous Coward | more than 3 years ago | (#35337850)

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.

## Re:Let me ask a "stupid" question (1)

## KnownIssues (1612961) | more than 3 years ago | (#35337858)

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.

## Re:Let me ask a "stupid" question (2)

## CastrTroy (595695) | more than 3 years ago | (#35338096)

## Re:Let me ask a "stupid" question (1)

## TheCarp (96830) | more than 3 years ago | (#35338176)

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.

## Re:Let me ask a "stupid" question (2)

## Haedrian (1676506) | more than 3 years ago | (#35337860)

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.

## Re:Let me ask a "stupid" question (1)

## dunezone (899268) | more than 3 years ago | (#35337880)

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.

## Re:Let me ask a "stupid" question (1)

## bogaboga (793279) | more than 3 years ago | (#35338000)

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.

## Re:Let me ask a "stupid" question (1)

## bhagwad (1426855) | more than 3 years ago | (#35337940)

## Re:Let me ask a "stupid" question (2)

## tixxit (1107127) | more than 3 years ago | (#35338076)

## Re:Let me ask a "stupid" question (0)

## Anonymous Coward | more than 3 years ago | (#35338228)

Last I checked, I didn't see your name on the list of those entitled to know the secrets of the universe.

## Re:Let me ask a "stupid" question (1)

## mlush (620447) | more than 3 years ago | (#35338320)

## This guy ... (0)

## Anonymous Coward | more than 3 years ago | (#35337646)

Sounds like this guy needs needs some P.

OP || NP > - P

## Oh no (0)

## Anonymous Coward | more than 3 years ago | (#35337658)

Now we get to wade through the "I can prove it when N=1" posts all over again.

## A better heading (3, Funny)

## Anonymous Coward | more than 3 years ago | (#35337680)

Proof = No Proof

## Re:A better heading (1)

## kalirion (728907) | more than 3 years ago | (#35338042)

Well if you prove that A = Not A, you're certainly going to give mathematicians and physicists everywhere a heart attack.

## Do people have to be a 'crank' to try? (0)

## Anonymous Coward | more than 3 years ago | (#35337730)

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.

## Re:Do people have to be a 'crank' to try? (1)

## Dunbal (464142) | more than 3 years ago | (#35337826)

## Re:Do people have to be a 'crank' to try? (1)

## vlm (69642) | more than 3 years ago | (#35338330)

truly test the answer space

The problem is its both simple enough and high profile enough that it attracts cranks like moths to a flame, and stereotypically none of them have the ability to operate in an "answer space" even as large as high school algebra or maybe high school geometry.

Very much like the drunk whom loses their car keys in the dark alley, but decides to search under the streetlamp for the keys, "because the light is better under the lamp". It tends to be a bit of a waste of time. Having a billion drunks search under the streetlamp in parallel for the keys isn't going to help.

If someone solves P = NP, like most big problems its going to be solved by someone applying some recently discovered, or at least never before applied technique that only a specialist in that odd field would know, and without even expecting it'll happen the answer falls out of a related calculation. Its not going to be from a million monkeys randomly trying modifications of the quadratic formula.

## Mistake in Summary (4, Informative)

## Haedrian (1676506) | more than 3 years ago | (#35337818)

"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.

## Re:Mistake in Summary (1)

## FrootLoops (1817694) | more than 3 years ago | (#35337932)

## Re:Mistake in Summary (1)

## CastrTroy (595695) | more than 3 years ago | (#35338134)

## Re:Mistake in Summary (1)

## danlip (737336) | more than 3 years ago | (#35338324)

Computers in the real world (by which I assume you mean personal computers) can easily solve TSP for 10 cities. Maybe even 100. The threshold for feasibility of any NP problem depends on the size of the input. At some point it is feasible for all computers, and at some point it is not feasible even for the biggest computers.

A more precise definition would be "Turing-computable". TSP is computable. The halting problem is not.

## Re:Mistake in Summary (0)

## Anonymous Coward | more than 3 years ago | (#35338338)

Computers in the real world can currently solve every NP-complete problem with current algorithms.

## Re:Mistake in Summary (1)

## Anonymous Coward | more than 3 years ago | (#35338092)

MUCH longer than a few billion years. Known algorithms are O(2^n). 2^(1 million) is a very long time, even if you do a step every femtosecond.

## Two answers (0)

## rossdee (243626) | more than 3 years ago | (#35337846)

Either

N=1

or

P=0

## Re:Two answers (2)

## geminidomino (614729) | more than 3 years ago | (#35337974)

That just keeps getting funnier every time it's posted (Which is about 30 times in any P =? NP story.)

## Re:Two answers (0)

## Anonymous Coward | more than 3 years ago | (#35338162)

Yeah, and it is obviously wrong. N and NP are sets, not scalars.

Even if you intentionally misinterpret the problem, there are more creative ways of doing it. How about P being a column vector and N a square matrix? Then P is an eigenvector of N with the eigenvalue 1.

## "very far from the sort of crank" (1)

## johnwbyrd (251699) | more than 3 years ago | (#35337848)

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.

## Proof.. (1)

## mehrotra.akash (1539473) | more than 3 years ago | (#35337884)

## Re:Proof.. (1)

## L4t3r4lu5 (1216702) | more than 3 years ago | (#35338060)

So, it has been proved that it is not possible to prove something we may or may not be able to prove?

No. It's been proven that this one proof is not a complete proof. There may be other proofs which will be proven to be proofs.

## This will NOT break all encryption algorithms... (1)

## Anonymous Coward | more than 3 years ago | (#35337892)

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.

## russian failure (0)

## Anonymous Coward | more than 3 years ago | (#35337896)

his errors are obvious really, anyone with a college degree who browses his would could have caught them easily.

## Romanov (1)

## Grizzley9 (1407005) | more than 3 years ago | (#35337920)

## So... (1)

## brian0918 (638904) | more than 3 years ago | (#35337922)

## Re:So... (1)

## drb226 (1938360) | more than 3 years ago | (#35337956)

## Re:So... (3, Funny)

## brian0918 (638904) | more than 3 years ago | (#35338248)

## This will NO break any encryption algorithms... (-1, Flamebait)

## RapidDemon (869604) | more than 3 years ago | (#35337926)

## Re:This will NO break any encryption algorithms... (1)

## Anonymous Coward | more than 3 years ago | (#35338172)

Citation please?

## Re:This will NO break any encryption algorithms... (1)

## Rakshasa Taisab (244699) | more than 3 years ago | (#35338272)

And he's saying things that make absolutely sense to me, so I'll skip on the citations.

## Re:This will NO break any encryption algorithms... (1)

## lucag (24231) | more than 3 years ago | (#35338250)

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 [psu.edu] ) 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).

## Re:This will NO break any encryption algorithms... (2, Interesting)

## Anonymous Coward | more than 3 years ago | (#35338288)

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.

## P=?NP has nothing to do with cryptography (0)

## Anonymous Coward | more than 3 years ago | (#35337930)

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

## P == NP (-1, Redundant)

## VortexCortex (1117377) | more than 3 years ago | (#35337958)

Let's just do a bit of algebra..

State the problem.

P = NPI'm solving for N, so lets swap the equation around.

NP = PLet's isolate the N.

N = P/PSimplify the division.

N = 1Eureka! I've simplified the "Does P = NP?" problem down to just "Does N = 1?".

## Re:P == NP (1)

## nedlohs (1335013) | more than 3 years ago | (#35338044)

You ignored the P=0 solution, by assuming it wasn't in your third step..

## Re:P == NP (0)

## Anonymous Coward | more than 3 years ago | (#35338304)

No he didn't. He left out the 5th & 6th steps, which are:

5) ???

6) Profit!

## Re:P == NP (1)

## Haedrian (1676506) | more than 3 years ago | (#35338120)

P and NP are both sets.

## Re:P == NP (1)

## Fnord666 (889225) | more than 3 years ago | (#35338210)

Let's isolate the N.

N = P/P

if p == 0 then fail

## Understanding what P, NP and that ilk is (1)

## morcego (260031) | more than 3 years ago | (#35337960)

On the same blog, actually:

http://cartesianproduct.wordpress.com/2010/12/29/what-if-p-np/ [wordpress.com]