Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

No P = NP Proof After All

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

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

cancel ×

318 comments

Wow. (0, Offtopic)

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

That's like the worst article ... ever. No information at all.

Re:Wow. (0)

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

Wow, that's like the worst first /. post ever. Actually read the article...

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)

Seems obvious to me...

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)

We should concentrate on figuring out whether God likes poutine [qwantz.com] .

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)

Seriously? On Slashdot? People still value the pursuit of knowledge over here. I am sure your grandfather can understand that.

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 nonsense

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

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.

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

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

There are 5 related articles linked to the same article im sure you read that do exactly what you asked.

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)

What I first read in the equation was: To Park is Not to Park

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)

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

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)

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.

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)

That's what I was going for, yes, glad I achieved that lofty goal :)

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)

Yes, but the supermarket is in Venice.

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)

Solving hard math problems faster is better.

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)

Need proof that faster is better? Look at your computer. Now, Look at the computers of the 1960s. See?

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)

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.

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

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

You think wealth is not defined by economic strength, but by its 1st derivative, the economic growth?

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

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

Yes. Anything but profit that doubles every quarter, forever, is a catastrophic failure.

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)

My computer IS from the 1960s, you insensitive clod!

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)

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.

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)

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.

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

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

Even if P != NP, that process can and will be sped up significantly with better algorithms and techniques.

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)

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.

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)

I'm going to break a cardinal rule of slashdot here...

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

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)

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.

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)

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?

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)

One of the funniest comments ever!

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

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

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.

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)

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.

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)

er no, pseudo-science, or "fake" science, by definition is not part of science.

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)

I read it as "unsolvable" in the sense that computers in the real world cannot currently solve them with current algorithms, instead of unsolvable in the abstract sense of, for instance, a Turing machine with unlimited steps and tape solving them in a finite number of steps. But, I agree that the wording is imprecise.

Re:Mistake in Summary (1)

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

They can be solved, it just takes a long time. So current algorithms are just too inefficient. There are efficient heuristic algorithms, but they will only give you a good answer, not necessarily the best one, but for many problems, good is often good enough.

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)

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

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)

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.

So... (1)

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

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?

Re:So... (1)

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

Yep. It's like twitter++

Re:So... (3, Funny)

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

Next the Slashdot story will be used as a Reliable Source on Wikipedia.

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

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

Not to burst anyone's bubble, but the factoring problem is actually not known to be NP completely and evidence points to the fact that it is not, since if it could be shown to be then this would prove that NP=Co-NP. This would be a surprising result since it would prove that the graph isomorphism problem is in 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

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)

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.

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)

I'd say the problem hinges on whether or not N is equal to one.

Let's just do a bit of algebra..

State the problem.
P = NP

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

Let's isolate the N.
N = P/P

Simplify the division.
N = 1

Eureka! 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

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...