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!

Polynomial Time Code For 3-SAT Released, P==NP

CmdrTaco posted more than 3 years ago | from the heard-this-before dept.

Programming 700

An anonymous reader writes "Vladimir Romanov has released what he claims is a polynomial-time algorithm for solving 3-SAT. Because 3-SAT is NP-complete, this would imply that P==NP. While there's still good reason to be skeptical that this is, in fact, true, he's made source code available and appears decidedly more serious than most of the people attempting to prove that P==NP or P!=NP. Even though this is probably wrong, just based on the sheer number of prior failures, it seems more likely to lead to new discoveries than most. Note that there are already algorithms to solve 3-SAT, including one that runs in time (4/3)^n and succeeds with high probability. Incidentally, this wouldn't necessarily imply that encryption is worthless: it may still be too slow to be practical."

cancel ×

700 comments

frrist psssot (-1, Troll)

Larry The Black Fag (812280) | more than 3 years ago | (#34940802)

for the jews

I'll be first to say WTF (-1, Offtopic)

alta (1263) | more than 3 years ago | (#34940832)

Damn you math geeks. Why must you come here and spew your incomprehensible formulas.

Re:I'll be first to say WTF (2)

ColdWetDog (752185) | more than 3 years ago | (#34940856)

Damn you math geeks. Why must you come here and spew your incomprehensible formulas.

I agree. Can we have a car analogy? Or at least Natalie Portman?

Re:I'll be first to say WTF (0)

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

Sure, I can do a Car analogy. So, you have a car doing 100 mph on a straight road. You get down on your hands and knees in the middle of the road with you head facing the oncoming car about bumper level. If the card hits you and kills you then P=NP, if it hits you and you do not die it is P!=NP, and it the guy driving swerves at the last minuet and completely misses you then the whole thing is wrong. Never said it would be right or make sense but I can make one up.

Re:I'll be first to say WTF (1)

Migala77 (1179151) | more than 3 years ago | (#34941046)

Damn you math geeks. Why must you come here and spew your incomprehensible formulas.

I agree. Can we have a car analogy? Or at least Natalie Portman?

Given a choice, I'd rather have Natalie Portman than a car analogy :)

Re:I'll be first to say WTF (0)

Noughmad (1044096) | more than 3 years ago | (#34941142)

I have nothing against NP, but what does P stand for?

Re:I'll be first to say WTF (5, Funny)

Qubit (100461) | more than 3 years ago | (#34941536)

what does P stand for?

Portman.

Oh wait, sorry, I was answering the comment above yours...

Re:I'll be first to say WTF (1)

morgan_greywolf (835522) | more than 3 years ago | (#34941250)

Car analogy:

Assuming that cars can be proven on a test track quickly, can the cars themselves also be built quickly?

Sorry. That's the best I can do.

Re:I'll be first to say WTF (5, Informative)

skeptikos (220748) | more than 3 years ago | (#34941338)

NP is short for Natalie Portman, and the car analogy follows:

Adleman's chief scientist, Nickolas Chelyapov, offered this illustration: Imagine that a fussy customer walks onto a million-car auto square and gives the dealer a complicated list of criteria for the car he wants.

"First," he says, "I want it to be either a Cadillac or a convertible or red." Second, "if it is a Cadillac, then it has to have four seats or a locking gas cap." Third, "If it is a convertible, it should not be a Cadillac or it should have two seats."

The customer rattles off a list of 24 such conditions, and the salesman has to find the one car in stock that meets all the requirements. (Adleman and his team chose a problem they knew had exactly one solution.) The salesman will have to run through the customer's entire list for each of the million cars in turn -- a hopeless task unless he can move and think at superhuman speed.

This serial method is the way a digital electronic computer solves such a problem.

Re:I'll be first to say WTF (1)

morgan_greywolf (835522) | more than 3 years ago | (#34941448)

Much better car analogy. Thank you. :)

Re:I'll be first to say WTF (4, Interesting)

dch24 (904899) | more than 3 years ago | (#34941342)

I like what's already posted. But here's another one:

I want to pick the lock on your car. It's one of those fancy code entry locks and I only have to press 3 buttons, but that's not really important.

Everyone has been saying that it's very, very hard (NP) to crack the code by trying combinations. Now there's a guy saying it's not quite as hard (P) and he wants everyone on the internet to check his work.

Re:I'll be first to say WTF (4, Interesting)

dch24 (904899) | more than 3 years ago | (#34941362)

I should add: mathematicians have been saying that NP is much, much harder than P, and it has always seemed logical to say that.

But if this guy can "crack the code" (that is, solve the 3-SAT problem), he has proven that NP is not harder than P.

The debate about whether NP is harder than P has been going for a long time.

Re:I'll be first to say WTF (-1)

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

Why do "anonymous reader"s submit sensationalist stories about unverified claimed solutions to famous open math problems?
I know I'm posting AC, but I still guarantee this solution is wrong, just like all the others.
All the experts in the field agree that P != NP, and that a proof will require completely new ideas.

And the vague reference to "encryption" in TFS is silly; there aren't any crypto algorithms in use whose security rests on P != NP.

Re:I'll be first to say WTF (1)

bersl2 (689221) | more than 3 years ago | (#34940972)

Well, it's certainly true that if no one reads, no one (except the author, which is unlikely) can yet say that it is false.

Re:I'll be first to say WTF (4, Informative)

TheRaven64 (641858) | more than 3 years ago | (#34941004)

All the experts in the field agree that P != NP

Absolutely untrue. All experts in the field that I've spoken to think that P is probably not equal to NP, but that a proof either way is going to be very hard.

Re:I'll be first to say WTF (4, Informative)

bluefoxlucid (723572) | more than 3 years ago | (#34941134)

And the vague reference to "encryption" in TFS is silly; there aren't any crypto algorithms in use whose security rests on P != NP.

Every symmetrical encryption algorithm in the field currently relies on the idea that the computation of the plaintext from the ciphertext and key is easily verifiable, but the computation of the key from the ciphertext is hard. Many can be analyzed if you can perform same difficult mathematics in a short time.

Every asymmetrical encryption algorithm in the field relies on the factoring problem, which is NP hard. If P==NP, then suddenly we know the factoring problem is NP easy. Further, solving one NP hard problem would effectively supply new strategies to solve other NP hard problems. QED.

Encryption relies on the theory that some shit is just hard to do. Not that we don't know how, but that from what we know it's trivially doable but takes too god damn much work that can't be done in any shorter than a huge fucking length of time even with all the resources in the world pointed at it.

Re:I'll be first to say WTF (1)

KublaiKhan (522918) | more than 3 years ago | (#34941318)

At least atmospheric-noise-derived one time pads will still be valid. Pity to have to go to that, though.

Re:I'll be first to say WTF (2)

HarrySquatter (1698416) | more than 3 years ago | (#34941186)

there aren't any crypto algorithms in use whose security rests on P != NP.

You mean except RSA?

Re:I'll be first to say WTF (1)

morgan_greywolf (835522) | more than 3 years ago | (#34941472)

More like except virtually any PKI algorithm. RSA is not alone in this.

Re:I'll be first to say WTF (0)

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

"All the experts agree" means nothing if there is a mathematical proof otherwise. 2 is not equal 2 because of a consensus.

Re:I'll be first to say WTF (1)

spud603 (832173) | more than 3 years ago | (#34941382)

Gotta take issue with this. The assertion that 2==2 is getting down to the axiomatic level, which means that yes, it is based on consensus. Or at least it is not too many steps removed from an axiom that is based on consensus.

Re:I'll be first to say WTF (0)

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

Axioms have nothing to do with consensus. There is nothing as fixed axioms on which people agree.
Different axioms just give you different mathematics.
Axiomatic is just the step-stone of a theory but you can pick any axioms you want.

Re:I'll be first to say WTF (2)

mark-t (151149) | more than 3 years ago | (#34941234)

Interesting. You claim you can guarantee that it is wrong, but you offer no proof to that effect. I am compelled to suspect, therefore, that you do don't know what it actually means to "guarantee" something.

It may very well be wrong, and it almost certainly actually is, but unless you could offer a proof to that effect, your claim of guaranteeing it to be so is wholly meaningless.

If, however, you've been holding out on us and do actually possess such a proof, then please, either present it here or post a link to it.

Re:I'll be first to say WTF (1)

Imagix (695350) | more than 3 years ago | (#34940934)

OK, I'll admit that I don't know what 3-SAT is, but P==NP (discussion of, not proof of....) should be covered in a Computing Science degree....

Re:I'll be first to say WTF (1)

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

Ok, let's see if we can clear the fog a little:

3-SAT is a special case of the boolean formula satisfiability problem, i.e. finding a valuation for a set of boolean variables so that the formula is satisfied.

"P" is a class of problems which take an amount of time to solve that is bounded by a polynomial expression in the size of the problem. For example, sorting a list of n elements with a commonly used sorting algorithm takes n*log(n) units of time.

"NP" is a class of problems which can be solved in polynomial time on a non-deterministic automaton. A problem is called NP-complete if there is a polynomial time algorithm which transforms it into another problem which is known to be NP-complete. That means if you can find a solution for an NP complete problem that runs in polynomial time on a deterministic machine, then you can also find such a solution for all NP complete problems. Famous NP complete problems include the aforementioned boolean formula satisfiability problem and the traveling salesman problem, where the task is to find the shortest route for visiting a number of locations and returning to the starting point.

So far, most people believe NP to be a larger class of problems than P, i.e. P not equal NP.

All of this is computer science, which many believe to be applied math, so let's not argue about that.

Re:I'll be first to say WTF (1)

vux984 (928602) | more than 3 years ago | (#34941296)

"3 SAT" is just a boolean expression

SAT are a class of problems of "is this boolean expression satifiable" or "is there a truth value (true/false) that we can assign each variable such that the boolean expression is true. "-a and a" is not satifiable for example.

3 SAT is just a special case of the general sat problem in that its structure of the expression to evaluate is precisely:

(a or b or c) and (-a or b or -e) and ("another clause with exactly 3 variables") and ("another clause with exactly 3 variables")... and so on.

Re:I'll be first to say WTF (-1)

imakemusic (1164993) | more than 3 years ago | (#34941308)

Are we expected to get a CS degree before reading Slashdot?

[I know what P!=NP means but only because I read into it after reading a previous Slashdot article.]

Re:I'll be first to say WTF (1)

abigor (540274) | more than 3 years ago | (#34941476)

Are we expected to get a CS degree before reading Slashdot?

Can you imagine how much better this place would be if that were the case?

Re:I'll be first to say WTF (4, Insightful)

TheCycoONE (913189) | more than 3 years ago | (#34941480)

Well there probably should be at least one refuge where computer science nerds can discuss news that matters. Unlike mainstream media the news here shouldn't have to pander to the lowest common denominator - if you don't care for this article move on to one in a field that you are interested in. If you are not a nerd at all then news for nerds may not appeal to you.

Re:I'll be first to say WTF (1)

jandrese (485) | more than 3 years ago | (#34941486)

Are we expected to get a CS degree before reading Slashdot?

Yes. Any other questions?

Re:I'll be first to say WTF (4, Funny)

TheRaven64 (641858) | more than 3 years ago | (#34941520)

Are we expected to get a CS degree before reading Slashdot?

Yes. And a PhD before posting. Didn't you read the T&Cs?

Re:I'll be first to say WTF (1)

watermark (913726) | more than 3 years ago | (#34940984)

The P vs. NP complete problem was introduced in a mandatory class at Virginia Tech (studying for Computer Science). Math is a big part of a CompSci degree now-a-day.

Re:I'll be first to say WTF (1)

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

Computer science IS math. It's the study of computability.

"Computer science is no more about computers than astronomy is about telescopes." - Edsger Dijkstra

Re:I'll be first to say WTF (2, Insightful)

HarrySquatter (1698416) | more than 3 years ago | (#34941228)

Math is a big part of a CompSci degree now-a-day.

lolwut? Since when has math NOT been a big part of computer science when computer science is a branch of mathematics? You must conflate computer science with programming or software engineering.

Re:I'll be first to say WTF (3, Insightful)

sourcerror (1718066) | more than 3 years ago | (#34941044)

Please turn in your geek card. This is basic CS stuff.

Re:I'll be first to say WTF (0)

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

You being a geek requires a CS degree? Who knew.

Re:I'll be first to say WTF (0)

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

No, but this is basic CS stuff (not insofar that it is easy to understand, but easy to have an idea what it's about.) "P=NP?" is a famous problem, and solving it in the unexpected way might have an impact on many things that geeks care about.

Re:I'll be first to say WTF (0)

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

It's more CS than math, although of course CS is also based on math of course.

Re:I'll be first to say WTF (3, Informative)

emurphy42 (631808) | more than 3 years ago | (#34941114)

If you understand Turing machines and big-O notation (and if you claim to be a programmer, you should) and polynomials (and if you claim to understand big-O notation, you should):

  • P is the set of all problems that can be solved in O(some polynomial of n) using a Turing machine. This can still be obnoxiously difficult, e.g. O(n^1000000), but 1000000*n^1000000 is still better than O(e^n) if n gets high enough.
  • NP is the set of all problems for which an alleged solution can be checked in O(some polynomial of n). The N stands for "non-deterministic" - imagine hooking up the Turing machine to another machine that spits out random maybe-solutions.
  • NP-complete problems are the hardest ones in NP, in the sense that if any of them is in P, then everything in NP is in P - because translating a solution of a NP-complete problem to a solution of any other NP problem is itself O(some polynomial of n).

Re:I'll be first to say WTF (-1)

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

Big-O means an orgasm right? So, what does this news do on the front page? I thought this is a site for geeks.

Hard stuff, & I took some of it in DISCRETE Ma (0)

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

"Damn you math geeks. Why must you come here and spew your incomprehensible formulas." - by alta (1263) on Thursday January 20, @11:40AM (#34940832) Homepage

Heh, it is HARD, but not "incomprehensible": See, I recall those "P=NP" set theory type problems in DISCRETE MATH (part of CSC degree requirements alongside Calc - which the FUNNY PART is, I have yet to use that (@ least in Database/Information Systems type programming))...

While initially learning it, I also recall thinking to myself:

"DAMN, this stuff is tough!"

Mainly because in that type of "math" (discrete seemed to me a "mishmash" of MANY concepts like this one, logic, & more) you have to THINK/CONCENTRATE, like mad, & your answers are many times only CLOSE approximations as well.

APK

P.S.=> If you've ever seen the film "21" (about Johnny Chan, the poker player, from what I understand)? They're largely applying that portion of DISCRETE MATH in it (calculating the odds of an occurrence from a subset of possibles)... apk

Simple Explanation (1)

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

To give a nice simple explanation ...

You have a bunch of interesting problems, which currently can only be run in exponential time - making them infeasable.
The thing is, there is no proof that they are only exponential - AND every problem in this set can be converted to all other problems in that set.

So the first person to solve one in Polynomial time solves all of them - and pretty much changes the world - including making encryption useless, and other things very effective - such as bin packing, travelling through a number of nodes (TSP) and other things.

Re:Simple Explanation (0)

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

So, is there a way of finding prime numbers by first translating the problem to 3-SAT ?

Re:Simple Explanation (1)

somersault (912633) | more than 3 years ago | (#34941582)

making them infeasable.

For large data sets at least. Algorithms that require O(n^2) time to run can still potentially be useful for small sets of data.

I hope I used that correctly. I get the concept, but I always forget the notation!

Re:I'll be first to say WTF (3, Funny)

UnknowingFool (672806) | more than 3 years ago | (#34941460)

Like you, I have no idea what the article or summary means. Unlike you, in the finest traditions of slashdot, I will have strong opinions here shortly like I have in many other subjects. Abrasive, irrefutable, and loud ones.

Probably Wrong but Clearly Falsifiable (5, Interesting)

eldavojohn (898314) | more than 3 years ago | (#34940840)

Even though this is probably wrong, just based on the sheer number of prior failures ...

Okay, so I'm going to agree with you that it's probably wrong. After reading the paper once last night in a sort of sleepy state, it's certainly a novel way of massaging each 3-Sat problem into an expanded space of memory (compact triplets structures) and then reducing this to solve the problem (all within polynomial time).

So the great thing about this paper is that it's short, it's not theoretical (which is a double-edged sword)/has been implemented (in Java, no less) and it's incredibly falsifiable. I'm not intelligent enough to poke holes in his proofs for this work but people can apply the code to DIMACS formatted [pdmi.ras.ru] problems to their heart's content and if they find one that produces the wrong answer then this is falsified.

I hope we find someone capable of commenting on the proof involving the transformation of the problem from compact triplets formula to compact triplets structure and the hyperstructures presented in the paper. If this is legit, the 3-Sat problem is one that more complex problems are reduced to in order to show that said complex problems are NP-complete. And that's something that's been proved by the Cook-Levin theorem [wikipedia.org] and given in the classic Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson.

Refreshingly tangible implementation, if I may say so myself!

Russia (-1)

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

It's amazing how many math and physics geniuses come out of Russia and other Slavic countries.

Makes me wish I drank vodka as a kid!

Well, it's obviously the vodka!

What, exactly, is 3-SAT? (3, Insightful)

gman003 (1693318) | more than 3 years ago | (#34940872)

I tried to look the problem up on Wikipedia, and all I got was inscrutable high-level math. From what I can gather, I seems like something that could be explained in layman's terms. Would someone be kind enough to do so?

Re:What, exactly, is 3-SAT? (2)

characterZer0 (138196) | more than 3 years ago | (#34940932)

Did you read the whole page, or just the 3-SAT section? Starting from the beginning of the article, I think it was explained simply enough.

Re:What, exactly, is 3-SAT? (-1, Flamebait)

bhcompy (1877290) | more than 3 years ago | (#34940944)

No, because that would make it accessible. This shit is like the latin Bible in the Dark Ages

Re:What, exactly, is 3-SAT? (4, Funny)

gman003 (1693318) | more than 3 years ago | (#34941290)

Linguam romanae scio. Latina difficila non est; ego in annis tribus didici.

Re:What, exactly, is 3-SAT? (-1, Offtopic)

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

It's a TV station, something similar to Fox News, only broadcast in Durcadurcastanese, yet curiously available in almost any country on earth (the Isle or Man appears to be an exception, there may be others). Their logo is a black and white micro-cloud formation - quite distinctive, I think you'll agree.

Re:What, exactly, is 3-SAT? (0)

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

It's actually a satellite-broadcasted Austrian TV station, an offshoot of the ORF.

Re:What, exactly, is 3-SAT? (1)

cpghost (719344) | more than 3 years ago | (#34941206)

There's indeed a 3SAT [3sat.de] TV station. Not to be confused with the 3-SAT problem [stanford.edu] .

Re:What, exactly, is 3-SAT? (5, Informative)

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

It is indeed quite simple. Imagine a long string of operators like this (! is "not"):
(x1 or x4 or !x3) and (x1 and !x4 and x3) and (x2 or !x1 or !x4) etc.
The question is "Is there a way to assign true/false to all the variables such that the end result is true".

This is a satisfiability problem (SAT), and what makes it 3-SAT is that it has three variables per clause.

Re:What, exactly, is 3-SAT? (2, Informative)

emt377 (610337) | more than 3 years ago | (#34941130)

I tried to look the problem up on Wikipedia, and all I got was inscrutable high-level math. From what I can gather, I seems like something that could be explained in layman's terms. Would someone be kind enough to do so?

3-sat: a series of 3-term clauses, of the form: _clause1_ AND _clause2_ AND ... _clauseN_. Each clause[i] consists of (term1 OR term2 OR term3). Each term may be negated. The same term may appear in multiple clauses. The problem: find all solutions where this evaluates to true, if any. (Find the solution space.) An exhaustive search of the term space is NP-complete (this ought to be obvious).

Not a complicated problem to understand, at all. And a fairly useful one to solve. Since boolean logic isn't linear, gaussian reduction and elimination can't be used.

Re:What, exactly, is 3-SAT? (1)

gman003 (1693318) | more than 3 years ago | (#34941316)

Ah. Thank you.

Re:What, exactly, is 3-SAT? (1)

token0 (1374061) | more than 3 years ago | (#34941182)

3-SAT: for a given formula of the form
(x[1] and !x[5] and x[2]) or (!x[1] and x[3] and x[6]) or ...
tell me if there is such an x[], that the formula is true.

So it's SAT with the (and) clauses limited to three variables. It turns out that it's an equivalent problem.

What's important is that if 3-SAT is solvable in polynomial time, all NP problems can be solved in polynomial time. And a pretty big part of complexity theory crumbles to obvious equalities, but that would only be sad for scientists :)

Re:What, exactly, is 3-SAT? (5, Informative)

debrain (29228) | more than 3 years ago | (#34941188)

Sir –

I did some graduate research on satisfiability [wikipedia.org] , so perhaps I can offer some illumination.

Satisfiability is a logic problem. Given a set of clauses that "or" a set of literals, which literals (and clauses) may be true or false, all "and"ed together, the question is: is there a set of literals (when true or false) that result in the overall statement being true. E.g.

X = (A or B) & (!A or !B) & (A or !B)

The question is: Is there a combination of A and B being true or false that would result in X being true? (In this example, X is true when A is true and B is false.)

3-SAT is satisfiability but with only 3-literals per clause e.g.

X = (A or B or C) and (A or !B or !C) and (!A or B or C) ...

There's a polynomial-time mapping from any satisfiability problem to 3-SAT, as there is between all NP complete [wikipedia.org] problems, which mapping is why they are so-classified. In other words, if you solve one NP complete problem in polynomial time (namely big-O notation O(ax^n) where n is the complexity i.e. number of literals) you solve them all in polynomial time. The most famous of these NP complete problems is probably the Knapsack problem [wikipedia.org] , though there are quite a few [wikipedia.org] .

All to say, it's a logic puzzle that has quite a few applications but no simple solution yet.

I'm not sure if the above is in layman terms, but I hope it is somewhat helpful.

Re:What, exactly, is 3-SAT? (4, Informative)

debrain (29228) | more than 3 years ago | (#34941512)

Correction: the big-Oh should be O(m*n^c), where c is a number that does not increase with the complexity of the input, though `n` and 'm' may.

Usually the size of the input increases complexity, but I believe in the case of satisfiability that complexity is proportional to the number of Horne clauses - clauses with at most one positive literal - because of difficulties reducing Horne clauses. I seem to recall that reducing Horne clauses to non-Horne clauses is itself a NP complete problem, everything else (which is severable) in determining satisfiability is provably polynomial.

In Vlad's proof he's found a solution to NP problems that are O(m * n^4).

Re:What, exactly, is 3-SAT? (1)

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

3-Sat is the 3 satisfiability problem. Basically, given a list of n boolean (true/false) variables and a string of 3 term clauses constructed on these variables, we wish to be able to decide whether there exists some some assignment of the variables that results in the entire string being true. A 3-term clause would be something like (x1 or x4 or ~x5) where ~ is the not operator, so one instance would be something like:

(x1 or x4 or ~x5) and (~x1 or x2 or ~x4) and (x1 or ~x3 or x5) which 11111 would satisfy.

3-Sat is known to be NP complete, so a polynomial algorithm for solving it could be adapted to create polynomial algorithms for all other NP complete problems.

Re:What, exactly, is 3-SAT? (0)

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

Take a number of propositions, A, B, C, ... whatever. Each of these can either be true or false, but we don't commit to which yet. Now, construct an arbitrary sequence of more complex yes-no questions, each involving three of the propositions. For example:

A or not C or Q? (true if A is true, c is false or Q is true)
not B or F or Z? (true if B is false, F is true, or Z is true)
etc.

Now, for this sequence of complex yes-no questions you've generated, determine if there is some assignment of true and false to each proposition (A is true, B is false, C is false, D is true, ...) so that the answer to each of the complex questions is "yes".

The problem of determining whether there is such an assignment of true and false to each of the propositions that makes every complex question true is the 3-SAT problem. It's called 3-SAT because each complex question has three propositions. It's been shown that if there is a way to find an answer (or determine there is no answer) to a 3-SAT problem with N questions in time polynomial in N (i.e. the time it takes is proportional to N, N squared, N cubed, etc.) then a huge class of problems become "tractable" - able to be solved in a reasonable amount of time. Among these are the famous "traveling salesman problem". It also means many common encryption schemes can be cracked.

It is generally thought that these types of problems take time exponential (or at least super-polynomial) in the size of the problem to solve, so they become rapidly intractable for large problems. For example, if a problem takes time proportional to 2^N to solve a question of size N, then even if you could do 1000 computations a second, a problem with 70 elements would take longer than the current age of the universe to solve.

P=NP (-1, Offtopic)

OverlordQ (264228) | more than 3 years ago | (#34940928)

P=NP IFF N is equal to 1.
QED

Next problem?

Re:P=NP (1)

mark-t (151149) | more than 3 years ago | (#34940996)

'N' doesn't 'equal' anything... it stands for "non-".

Re:P=NP (0)

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

No it doesn't. In this case, it stands for nondeterministic.
en.wikipedia.org/wiki/NP_(complexity)

Re:P=NP (1)

mark-t (151149) | more than 3 years ago | (#34941344)

Okay... fair enough...

Outside of quantum computers, do nondeterministic turing machines even exist?

Re:P=NP (0)

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

Stop reinforcing the stereotype that math geeks have no humor.

Re:P=NP (1)

DoofusOfDeath (636671) | more than 3 years ago | (#34941020)

If n = 1, not just N == 1.

Re:P=NP (1)

DoofusOfDeath (636671) | more than 3 years ago | (#34941040)

Damn HTML. Let me try this in Fortran instead:

IF N .LE. 1, not just IF N .EQ. 1

Re:P=NP (0)

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

P=NP IFF N is equal to 1.
QED

Next problem?

See? This is the problem with Dunning-Kruger mathematicians. P could just as well be 0.

Re:P=NP (0)

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

Yep the IFF is mistated since P = 0 with N = any number statisfies the equation.

Re:P=NP (1)

sqlrob (173498) | more than 3 years ago | (#34941088)

Nope. There's a case where N can be any value.

Re:P=NP (0)

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

Actually "IFF" is incorrect. If N != 1 and P = 0 then your hypothesis is falsified. You should have written "IF".

Re:P=NP (0)

Migala77 (1179151) | more than 3 years ago | (#34941096)

P=NP IFF N is equal to 1. QED

Next problem?

or P=0

Re:P=NP (1)

kwerle (39371) | more than 3 years ago | (#34941198)

P=NP IFF N is equal to 1.
QED

Next problem?

You're being silly, but I can think of one solution that works for any value of N, so I'm afraid you blew it.

Re:P=NP (1)

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

P and NP are sets...

Re:P=NP (0)

eggnoglatte (1047660) | more than 3 years ago | (#34941258)

Haha. Never heard that joke before. </sarcasm>

Re:P=NP (0)

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

Great! Now prove that N = 1, or, alternatively, that N != 1.

Turns out that that is the hard part, since we don't know what makes something NP, we just know about a whole bunch of problems that seem to be similarly hard.

Re:P=NP (0)

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

Or P=0 and N=anything.

Therefore you fail alegbra.

QED

encryption (4, Informative)

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

Incidentally, this wouldn't necessarily imply that encryption is worthless: it may still be too slow to be practical.

No, it means good encryption will be much less practical. Computers will always get faster so "too slow" is not a good argument. If P != NP you can always make encryption too hard to break by increasing the key size - the cost to encrypt and decrypt only goes up polynomial with key size but cost to break it goes up exponentially, which makes it too hard even for those with supercomputers. If P = NP it means the cost to break it only goes up polynomially. This put the cost to encrypt in the same realm as the cost to break. So you can use much bigger keys but it becomes more expensive and may stop petty criminals but won't stop people with supercomputers.

Re:encryption (1)

pavon (30274) | more than 3 years ago | (#34941294)

Yeah, but if the order of the the polynomial is say, 2 million, then you can still pick key sizes that are so computationally expensive to break as to be secure for all practical purposes.

Re:encryption (4, Interesting)

mr exploiter (1452969) | more than 3 years ago | (#34941366)

You really don't know what are you talking about, don't you? Here is a counter example: assume the encryption/decryption is O(n^2), assume the cryptanalysis is O(n^3), that is, polynomial. You can choose n so that the cryptanalysis is arbitrarily more difficult than the encryption, so this result alone (if it's true) doesn't mean a thing for crypto.

Re:encryption (1)

TheL0ser (1955440) | more than 3 years ago | (#34941396)

but won't stop people with supercomputers.

If someone with a supercomputer is trying to break your encryption, I would think you have bigger problems to worry about.

Re:encryption (0)

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

Right because if there' one thing we learned from WW2 it's that cryptography never matteres.

Re:encryption (1)

currently_awake (1248758) | more than 3 years ago | (#34941548)

Or we stop using math based encryption. In a world of cheap bandwidth and cheap storage we can switch to one time pads. While A sends encrypted data to B using one time pad P1, new one time pads are sent from crypto server C to both A and B using separate encryption keys/pads. There is no math problem to solve, no way to determine the key. Not even quantum computing will help with this.

More like.... (-1)

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

8=====D

Interesting (0)

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

Has anyone figured out a proof that the backtracking is limited in some way that creates a polynomial bound? There are ample examples of problems where some backtracking occurs, and I'm wondering if it isn't possible to construct a problem class where it actually ends up going over a larger than polynomial portion of the search space.

Wow how silly it is to post code math on /. header (0)

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

Reading the submission in front was like trying to write ancient Greek in MS OFFICE! The summary made my ache and I felt like I was caught inside a 4/3 pi r cubed loop statement!

Nice way to spread malware? (-1)

nodan (1172027) | more than 3 years ago | (#34941292)

Did anybody check the software offered really does what it's supposed to do and not install something not so funny on your machine?

Re:Nice way to spread malware? (4, Insightful)

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

. . .

"he's made source code available"

Since checking the algorithm requires reading the source code - I would assume he's not spreading the source code of malware, because all interested parties WILL BE TRYING TO UNDERSTAND THE SOURCECODE.

Goldbach Conjecture (5, Funny)

Bazman (4849) | more than 3 years ago | (#34941350)

I have code for a solution to the Goldbach Conjecture, but it doesn't fit into my free storage on github....

Maybe 3-SAT isn't NP-complete (0)

Thundersnatch (671481) | more than 3 years ago | (#34941370)

Couldn't the existence of this working polynomial-time algorithm mean that the previous work which showed the 3-SAT problem to be NP-Complete was in error? That seems more likely than P==NP.

Re:Maybe 3-SAT isn't NP-complete (1)

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

Proving NP-completeness is a Mathematical process which involves performing a turing reduction on an NP-complete problem to the unknown problem (or the other way around, can't remember).

Its not like some guy went "Oh yeah! Its NP complete, because my lucky 8-ball said so"

Re:Maybe 3-SAT isn't NP-complete (4, Informative)

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

No.

Every NP-Complete problem is based off the fact that 3-SAT is NP-Complete (3-SAT was the problem used by Levin and Cook to introduce the concept of NP-Completeness). Ever since then, getting into the NP-Complete club has meant reducing 3-SAT to your problem of choice in polynomial time.

The theorem is actually fairly simple, but I can't remember it off the top of my head, and the wikipedia article doesn't help at all. Anyone care to update it?

Intel and AMD both hope P!=NP (1)

Algorithmnast (1105517) | more than 3 years ago | (#34941390)

If P==NP, then any company that wants to pump 10 mil into a fab building will be able to compete with their chip layout strategies.

Interesting... (3, Funny)

shadowrat (1069614) | more than 3 years ago | (#34941574)

I can't really comment on the validity of the claims in the article. It's unclear if he has indeed proven P==NP. I do know that this article clearly proves I am only of average or slightly sub average intelligence.
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...