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

Probably Wrong but Clearly Falsifiable by eldavojohn · 2011-01-20 04:40 · Score: 5, Interesting

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

--
My work here is dung.

Re:Probably Wrong but Clearly Falsifiable by dvdkhlng · 2011-01-20 06:12 · Score: 5, Interesting

Maybe I'm overlooking something, but to me it looks like they're doing the reduction to a polynomial-time problem already at the very beginning of the paper (I guess if there is a fault, there it hides). As soon as they go to "compact triplet" structure, the instance of 3-SAT is polynomial-time solvable using a trellis algorithm. Yes, very similar to the algorithm that is employed to decode convolutional codes.
In fact they're decomposing the initial 3-SAT problem into multiple "compact triplet" 3-SAT problems intersected using an AND operation. But as these intersected 3-SAT formulas use the same variables, without any interleaving (permutation) applied, the trellis algorithm still applies (just like solving for a convolutional encoder with > 1 check bits per bit).
Thinking once more about that: the compact triplet structure is clearly not general enough to express generic 3-SAT problems. This is like attempting to transform a quadratic optimization problem x^T*H*x involving a symmetric matrix H into a corresponding problem with a tri-diagonal matrix H.
The only way I see they could do the transform is by introducing exponentially many helper variables, thus moving the problem back into NP again. But it does not look like they're attempting something like that.
Re:Probably Wrong but Clearly Falsifiable by EuclideanSilence · 2011-01-20 06:34 · Score: 5, Informative

This is not a P=NP paper. The paper solves a problem of a related data structure in polynomial time (quartic time), then shows that it can be used to solve some cases of 3SAT. The 3 outputs the algorithm can give are "the formula is not satisfiable", "the formula is satisfiable" (and the solution is given), and "failure of classification" -- it couldn't solve the problem. The important question we wait for on the experts on this paper isn't "is it correct" (it probably is) but "how effective is it".
Re:Probably Wrong but Clearly Falsifiable by dvdkhlng · 2011-01-20 08:53 · Score: 2

This is not a P=NP paper. The paper solves a problem of a related data structure in polynomial time (quartic time), then shows that it can be used to solve some cases of 3SAT. The 3 outputs the algorithm can give are "the formula is not satisfiable", "the formula is satisfiable" (and the solution is given), and "failure of classification" -- it couldn't solve the problem. The important question we wait for on the experts on this paper isn't "is it correct" (it probably is) but "how effective is it".
In fact it does suffice to show that the algorithm determines satisfiability of a 3-SAT instance in polynomial time. Create a derived 3-SAT instance that adds a clause restricting one variable to value '1'. Then see whether it is still satisfiable. It is not? Ok, constrain the variable to '0', and add a constraint for the next variable. Is it now satisfiable? And on and on. You understand the pattern? For n variables it only takes O(n) time to turn the 3-SAT satisfiability testing algorithm into a 3-SAT solver. Or in CS terms: the 3-SAT decision problem is polynomial time reducable to the 3-SAT solving problem.

Re:I'll be first to say WTF by The+MAZZTer · 2011-01-20 04:41 · Score: 2

http://en.wikipedia.org/wiki/P==NP

Re:I'll be first to say WTF by ColdWetDog · 2011-01-20 04:41 · Score: 2

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?

--
Faster! Faster! Faster would be better!

What, exactly, is 3-SAT? by gman003 · 2011-01-20 04:42 · Score: 3, Insightful

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? by characterZer0 · 2011-01-20 04:46 · Score: 2

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.

--
Go green: turn off your refrigerator.
Re:What, exactly, is 3-SAT? by Anonymous Coward · 2011-01-20 04:55 · Score: 5, Informative

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? by Anonymous Coward · 2011-01-20 04:57 · Score: 2, Informative

Did you check the simple wiki?
http://simple.wikipedia.org/wiki/Boolean_satisfiability_problem
Re:What, exactly, is 3-SAT? by emt377 · 2011-01-20 04:59 · Score: 2, Informative

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? by debrain · 2011-01-20 05:02 · Score: 5, Informative

Sir –
I did some graduate research on satisfiability, 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 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, though there are quite a few.
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? by gman003 · 2011-01-20 05:08 · Score: 4, Funny

Linguam romanae scio. Latina difficila non est; ego in annis tribus didici.
Re:What, exactly, is 3-SAT? by debrain · 2011-01-20 05:22 · Score: 4, Informative

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? by hawkfish · 2011-01-20 05:40 · Score: 4, Informative

Linguam romanae scio. Latina difficila non est; ego in annis tribus didici.
Uh... I know the Roman language. Latin is not difficult; I learned it in three years.
?

--
You will not drink with us, but you would taste our steel? - Walter Matthau, The Pirates
Re:What, exactly, is 3-SAT? by marcosdumay · 2011-01-20 05:51 · Score: 3, Insightful

A small correction. The NP-Complete problem is "Is there any input for what it evaluates to true?". NP problems are exclusively yes/no ones.
Now, if you solve the SAT problem, you can derive an algorithm for calculating the solution space. It will probably take exponential time. You can also derive an algorithm for finding an input that evaluates to true in polynomial time.

--
Rethinking email
Re:What, exactly, is 3-SAT? by robthebloke · 2011-01-20 06:15 · Score: 3, Funny

No, i believe the correct translation is:

"Roman sharks, with frickin' laser beams attached to their latin heads".

But then again, I don't read latin much anymore, so I may have made the odd grammatical error...
Re:What, exactly, is 3-SAT? by Tenek · 2011-01-20 06:30 · Score: 3, Funny

Romanes eunt domus.
Re:What, exactly, is 3-SAT? by prionic6 · 2011-01-20 06:45 · Score: 5, Funny

If you're so good at it, at least translate the line for us!
smartass...
Re:What, exactly, is 3-SAT? by Carewolf · 2011-01-20 07:35 · Score: 2

When you talk about NP-complete problem you always refer to the decision version. 3-SAT and knapsack in their native forms are also not decision problems. All the problems are reformulated to decision problems to make them easier to compare and reason about for the purpose of establishing NP-completeness.
Oh damn, and now you made me be pedantic about shooting down being pedantic. I feel ironic.
Re:What, exactly, is 3-SAT? by Surt · 2011-01-20 07:53 · Score: 4, Informative

The clauses in 3sat are required to be disjunctions (OR).

--
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
Re:What, exactly, is 3-SAT? by Darinbob · 2011-01-20 08:10 · Score: 2

You have three satellites in space, each of which broadcasts a certain number of television programs but only one at a time. Your satellite receiver can only see a maximum of 2 satellites at a given instance, but will see all three of them during one 24 hour period. Now the 3-SAT problem is determining the probability that your favorite television math program will be pre-empted by a stupid football game.

Or something like that if I remember correctly.

Re:I'll be first to say WTF by TheRaven64 · 2011-01-20 04:52 · Score: 4, Informative

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.

--
I am TheRaven on Soylent News

Re:I'll be first to say WTF by sourcerror · 2011-01-20 04:54 · Score: 3, Insightful

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

Re:I'll be first to say WTF by emurphy42 · 2011-01-20 04:58 · Score: 3, Informative

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

encryption by danlip · 2011-01-20 04:59 · Score: 4, Informative

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 by emurphy42 · 2011-01-20 05:01 · Score: 2

Obligatory xkcd link
Re:encryption by mr+exploiter · 2011-01-20 05:13 · Score: 4, Interesting

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 by vadim_t · 2011-01-20 05:33 · Score: 2

If you encrypt a one time pad with anything else, it's only as strong as whatever you encrypted it with. So the one time pad is superfluous.
If you encrypt a one time pad with another, then that second one must have at least the same length as the first. So to transfer 1GB of data, you need 1GB of OTP, for which you need 1GB of another OTP, which is quite pointless.
It all comes to that OTPs are huge and exchanging them is a huge problem that's not practical for the vast majority of people.
Re:encryption by Chowderbags · 2011-01-20 05:46 · Score: 3, Informative

Also big-O notation can hide arbitrarily large constants. This is why, despite the Coppersmith-Winograd algorithm being the "fastest" matrix multiplication algorithm (in terms of having the lowest exponent), it still isn't used. The constant is so large that the only matrices that it would actually be faster for are way beyond the size that modern hardware can handle.
Re:encryption by dsrg · 2011-01-20 06:49 · Score: 2

Obligatory Charles Stross link

--
"Bees!" - Eddie Izzard

Re:I'll be first to say WTF by bluefoxlucid · 2011-01-20 04:59 · Score: 4, Informative

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.

--
Support my political activism on Patreon.

Re:I'll be first to say WTF by HarrySquatter · 2011-01-20 05:02 · Score: 2

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 by HarrySquatter · 2011-01-20 05:04 · Score: 2, Insightful

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 by mark-t · 2011-01-20 05:04 · Score: 2

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.

--
File under 'M' for 'Manic ranting'

Re:I'll be first to say WTF by skeptikos · 2011-01-20 05:11 · Score: 5, Informative

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 by dch24 · 2011-01-20 05:11 · Score: 4, Interesting

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.

Goldbach Conjecture by Bazman · 2011-01-20 05:12 · Score: 5, Funny

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

Re:Goldbach Conjecture by Darinbob · 2011-01-20 08:15 · Score: 2

Ah yes, like that proof of Fermat's Last Theorem someone tried to send me on twitter.

Re:Nice way to spread malware? by Haedrian · 2011-01-20 05:12 · Score: 4, Insightful

. . .

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

Re:I'll be first to say WTF by dch24 · 2011-01-20 05:12 · Score: 4, Interesting

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:Maybe 3-SAT isn't NP-complete by Anonymous Coward · 2011-01-20 05:18 · Score: 4, Informative

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?

Re:I'll be first to say WTF by UnknowingFool · 2011-01-20 05:19 · Score: 3, Funny

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.

--
Well, there's spam egg sausage and spam, that's not got much spam in it.

Re:I'll be first to say WTF by TheCycoONE · 2011-01-20 05:19 · Score: 4, Insightful

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 by TheRaven64 · 2011-01-20 05:22 · Score: 4, Funny

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

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

--
I am TheRaven on Soylent News

Re:I'll be first to say WTF by Qubit · 2011-01-20 05:24 · Score: 5, Funny

what does P stand for?

Portman.

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

--

coding is life /* the rest is */

Interesting... by shadowrat · 2011-01-20 05:27 · Score: 3, Funny

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.

Re:Interesting... by corbettw · 2011-01-20 06:47 · Score: 5, Funny

Welcome to the club. My friends and colleagues routinely think of me as "one of the smartest people they know" (or so I've been told). Articles like this remind me of my true status, which is helpful in not getting cocky.

--
God invented whiskey so the Irish would not rule the world.

Re:I'll be first to say WTF by deapbluesea · 2011-01-20 05:30 · Score: 5, Insightful

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.

Absolutely correct. The difference between say, computer science and sociology, is that computer scientists require absolute proofs. In other words, if you claim that P==NP, as this paper does, then I require you to show that it is so for all possible inputs.

The paper, in fact, does not show such a thing. To the contrary, it fails to show a sound and complete reduction of 3-SAT to hyperstructures, or CTF or CTS or whatever other acronyms were made up by the author. I'm not saying that he's wrong, simply that this is not a proof - it is only a claim. The author claims to have "proven" his algorithm is polynomial time by giving it a smattering of inputs and noting that the time the algorithm took to complete increased by a polynomial factor of the input size.

Clearly the author has not studied his algorithmic complexity texts well enough to understand the definition of Big-O. Big-O only claims that algorithmic growth is asymptotic to a given curve as the input size goes to infinity from some value n0. In other words, many algorithms may display linear growth to a point, and then become exponential after input size greater than n0. A statistical analysis will not prove anything. The author needs to do a full algorithmic analysis instead.

I predict this paper will be rapidly debunked and we will still not know if P==NP.

--
Government is not reason; it is not eloquent; it is force. Like fire, it is a dangerous servant and a fearful master.

Re:I'll be first to say WTF by kiwix · 2011-01-20 05:31 · Score: 4, Interesting

While you did a good job at explaining the general relation between NP-hardness and cryptography, there are several factual errors in your message. First, there are many asymmetrical encryption algorithm that are not based on factorization: many are based on the discrete logarithm, and other hard problems are used in a few construction. Second, we don't know whether factoring is NP-hard and it is conjectured not to be NP-hard (which does not mean we think it's polynomial!).

Also, you seem to have missed the point of NP-harder or NP-completeness: if we can sole one NP-hard problem in polynomial time, then by definition this proves that P=NP and we can solve all NP problems in polynomial time. (A problem is said to be NP-complete if it is NP-hard, and it is itself in NP)

Re:I'll be first to say WTF by Zediker · 2011-01-20 05:33 · Score: 3, Informative

Best car analogy i can think of is:

Is it easy to both plan a car trip and check that your car trip is planned well. If yes, the P=NP, if no, then P!=NP, if you cant determine either yes or no then its all wrong ;)

--
I love to slaughter the english language.

Re:P=NP by undecim · 2011-01-20 05:34 · Score: 2

And NS/. is a set as well. It is defined as the set of /.ers that do not understand sarcasm. I believe you have just proven that it is not empty.

--
The Internet has given stupid people the resources of intelligent people.

Re:I'll be first to say WTF by Zediker · 2011-01-20 05:35 · Score: 2

Best car analogy i can think of is:

Is it easy to both plan a car trip and check that your car trip is planned well.

If yes, the P=NP

if no, then P!=NP

if you cant determine either yes or no, then its all wrong ;)

--
I love to slaughter the english language.

Re:I'll be first to say WTF by Anonymous Coward · 2011-01-20 05:40 · Score: 3, Interesting

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.

No. You're neglecting the discrete log problem which underpins Differ Hellman. There are probably other esoteric algorithms that rest on other hard problems like the knapsack problem. And I believe you also misstated the RSA assumption.

The RSA assumption is that computing the Euler phi/totient function for n=p*q where p,q are prime is HARD*. The RSA assumption is RELATED to but NOT EQUIVALENT to factoring. The relationship is that RSA can be reduced to factoring, i.e., factor n into p,q and return phi(n)=(p-1)(q-1). That's a single direction. The reverse, a reduction from factoring to RSA/totient is NOT KNOWN to exist.

So you're correct in the sense that if factoring is easy, RSA is easy. If RSA is easy, factoring may still be HARD*. Reductions in both directions would prove "necessary and sufficient/if and only if".

*HARD has a technical definition that's not necessary for this comment.

Re:I'll be first to say WTF by geekoid · 2011-01-20 05:41 · Score: 2

You are expect to understand this site is for nerds. If you aren't a math nerd, then move to the next article. IF you want to be pandered to, do to a different site. I'll assume something Murdoch owns would suit your ilk.

If you want to understand, ask, or take a class.

do NOT whine that you don't understand it, so it shouldn't be here.

--
The Kruger Dunning explains most post on /. http://en.wikipedia.org/wiki/Dunning%E2%80%93Kruger_effect

Re:I'll be first to say WTF by sakonofie · 2011-01-20 05:44 · Score: 2

For more information about what experts think about P =? NP, check out Bill Gasarch's wonderfully entertaining poll: http://www.cs.umd.edu/~gasarch/papers/poll.pdf

Re:I'll be first to say WTF by geekoid · 2011-01-20 05:44 · Score: 4, Interesting

I predict the same thing; however how awesome would it be it the paper is correct!

I wouldn't use the term debunked. Shown to be incorrect is better. Which is fine and expected in science. To me ;debunked; implies some sort of fraud is taking place.

--
The Kruger Dunning explains most post on /. http://en.wikipedia.org/wiki/Dunning%E2%80%93Kruger_effect

Re:Nice way to spread malware? by undecim · 2011-01-20 05:47 · Score: 2

Next frontpage article title: "Malware Authors Target Computer Scientists with Complexity Theory"

--
The Internet has given stupid people the resources of intelligent people.

Re:I'll be first to say WTF by mrstrano · 2011-01-20 05:51 · Score: 3, Informative

That's exactly right!

Please read these two blog posts about the consequences of P=NP from an expert in the field:

http://rjlipton.wordpress.com/2009/09/18/why-believe-that-pnp-is-impossible/
http://rjlipton.wordpress.com/2009/02/18/insider-baseball-and-pnp/

Re:I'll be first to say WTF by jd · 2011-01-20 05:55 · Score: 2

I won't say every asymmetrical encryption algorithm relies on the factoring problem, as there are asymmetrical algorithms which are proof against even quantum computing attacks.

--
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)

Re:I'll be first to say WTF by sakonofie · 2011-01-20 05:59 · Score: 2

the factoring problem, which is NP hard.

Quick correction. The integer factoring problem is in NP, but is not known to be NP-hard. Here are a couple of explanations:
http://cstheory.stackexchange.com/questions/159/is-integer-factorization-an-np-complete-problem
http://en.wikipedia.org/wiki/Integer_factorization

Re:I'll be first to say WTF by SandFrog · 2011-01-20 06:01 · Score: 4, Funny

Maybe there wasn't enough space in the margin.

--
Contentment is the greatest wealth
- Sukhavagga Dhammapada
Contentment is the goal behind all goals.

Re:I'll be first to say WTF by daremonai · 2011-01-20 06:05 · Score: 4, Funny

Here you go: Let's say you want to have sex with Natalie Portman (NP). Up until now, it was generally assumed that meant you had to satisfy three conditions: be rich, handsome, and fascinating. Unfortunately, any one of those would leave out the vast majority of people on this list; satisfying all three (3-SAT) was considered virtually impossible.

But now, Romanov claims that it is sufficient merely to say the mathematical equivalent of "Please" (P). Naturally, people are skeptical.

Re:I'll be first to say WTF by bunratty · 2011-01-20 06:20 · Score: 5, Informative

You left out the most important part. It takes lots of work to find the car, but it takes a short time to check that it's the right car once it's found. In other words, if you're lucky and always guess the right car on your first try (in other words nondeterministically), you can check that it's the right solution quickly (in polynomial time). Nondeterministic polynomial time = NP.

In 3-SAT, it takes exponential of time to find the assignment to the variables that satisfies all the conditions, but it takes polynomial time to check whether a particular assignment is correct. It takes exponential time to factor a product of two large primes, but it takes polynomial time to make sure it's the correct factorization.

--
What a fool believes, he sees, no wise man has the power to reason away.

Re:I'll be first to say WTF by deapbluesea · 2011-01-20 06:23 · Score: 2

Good call. You're right. It will be shown to be a false claim. I never intended to imply that the author is intentionally misleading anyone, only that his methods are not rigorous enough to prove his claim.

--
Government is not reason; it is not eloquent; it is force. Like fire, it is a dangerous servant and a fearful master.

Re:Am I Confused? by gall0ws · 2011-01-20 06:32 · Score: 2

NP: set of problems you can solve in polynomial time on a non-deterministic Turing Machine
P: ...on a deterministic TM

Any problem in NP can be reduced to an NP-Complete problem (clique, vertex cover, 3-SAT, etc...) in polynomial time.

So, if you have an algorithm to solve an NP-Complete (like 3-SAT) problem in p(n) on a deterministic Turing Machine then you have NP == P.

--
| (ceci n'est pas une pipe)

Re:I'll be first to say WTF by EllisDees · 2011-01-20 06:35 · Score: 4, Insightful

Not to get completely off the subject, but there are many perfectly understandable proofs of why 0.999... = 1. For instance, one of the things that defines what a real number is that it is not exactly the same as a different number. Seems pretty common sense, huh? So what number, exactly, comes between 0.999... and 1? Like you said, those 9s go on forever, so if there is nothing that you can add to the first term to turn it into the second, they must be the same. They are just 2 different ways of expressing the exact same number. You probably don't have a problem with the idea that 1/3 = .333..., so multiply both sides by 3 and what do you get?

There's even a wikipedia page that I'd totally paste in here if Chrome was able to do so.

--
-- Give me ambiguity or give me something else!

Re:I'll be first to say WTF by Frank+T.+Lofaro+Jr. · 2011-01-20 06:37 · Score: 2

If you have a secure channel to transmit the one time pad, you could use that for the message instead and not need encryption.

--
Just because it CAN be done, doesn't mean it should!

Re:Am I Confused? by betterunixthanunix · 2011-01-20 06:37 · Score: 2

P is defined as the set of decision problems that can be solved by a deterministic Turing machine in polynomial time. NP is the set of decision problems that can be solved by a non-deterministic Turing machine in polynomial time. NP-Complete problems are problems in NP such that the existence of a deterministic polynomial time algorithm to solve any one of the NP-complete problems would imply that P=NP; any NP complete problem can be reduced to any other NP complete problem in polynomial time.

--
Palm trees and 8

Re:I'll be first to say WTF by snowgirl · 2011-01-20 06:40 · Score: 5, Funny

And if each car is located in a different city, then he'll have to go travelling in order to test all the criteria. Of course, he wouldn't want to end up hitting the same city twice...

--
WARNING! This girl exceeds the MAXIMUM SAFE standards established by the FDA for BRATTINESS

Re:I'll be first to say WTF by pipatron · 2011-01-20 06:40 · Score: 5, Informative

there's a 9 at the end

This is why your understanding fails. There is no end.

What is really so complicated by these simple examples:

1/3 + 1/3 + 1/3 = 3/3 = 1

And since 1/3 exactly equals 0.333... we have:

0.333... + 0.333... + 0.333... = 0.999...

And since the two sums are exactly equal, 0.999... equals 1. It's not really that magic, and your normal daily life will not be affected. It is, however, true.

--
c++; /* this makes c bigger but returns the old value */

Re:I'll be first to say WTF by networkBoy · 2011-01-20 06:40 · Score: 2

In fact to the authors credit, he knows this is a big claim, so he's posting everything and saying: "Check this out". As opposed to several other "I have proof" people who when asked to show their work, say "no"

--
whois gawk date unzip strip find touch finger mount join nice man top fsck grep eject more yes exit umount sleep dump

Re:I'll be first to say WTF by commander_gallium · 2011-01-20 06:40 · Score: 2

Can anyone explain to me how someone would even believe this particular statement?

Sure. Think about 1 - 0.999... it gives you 0.000... = 0. You might worry about a 1 sitting out there in the "infiniteth" decimal place, but remember that you can never get there; the 1 never happens. Since 0.000... = 0 then 1 - 0.999... = 0 and 0.999... = 1. Nothing fancy.

Re:I'll be first to say WTF by BrotherBeal · 2011-01-20 06:42 · Score: 4, Informative

Take a look at it through a fairly simple algebraic proof.

1.) 0.99999... * 10 = 9.99999... // decimal multiplication by 10 means we just shift to the left and the infinite decimal expansion isn't affected.

2.) 9.99999... - 0.99999... = 9 // the infinite decimal expansion is still a number and there's no reason we can't subtract it.

3.) 9 / 9 = 1 // if we take the difference from the above subtraction and "undo" the multiplication in step 1, we need to divide by 9 because we've just removed one of what we multiplied.

Therefore 0.99999... = 1. Q.E.D.

--
I'm disabling ads until because I choose not to reward redesigns that are less usable than "view source".

Yuk! by elsurexiste · 2011-01-20 07:04 · Score: 2

I saw code like this when I worked on an implementation of Levenberg Marquardt that I had to migrate, on a neural network toolkit, and on an Ant Colony Optimization program I ended up optimizing. It's full of needless interfaces and classes, and it's too objectified to be understandable. Usually, I throw everything away and start from scratch.

By the way, I'll give credit where credit is due: if the algorithm is what it's stated, then let congratulations be given to them. Until then, all I see is a yucky mess.

Never send a comp-sci to do an engineer's work.

--
I rarely respond to comments. Also, don't ask for clarifications: a brain and Google are faster, believe me!

Re:My personal wild guess by Anonymous Coward · 2011-01-20 07:13 · Score: 2, Insightful

You should read a little bit more about complexity theory and debunk your idea that because there are easy solutions to some problems for some sizes the solutions scale.

Your Math is Minimal by luis_a_espinal · 2011-01-20 07:19 · Score: 2

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.

Math shmath. It's much more logic than math.

It is Axiomatic Mathematical Logic, a branch of Mathematics. So to say CS is "more logic than math" does not make any sense, unless you are conflating Axiomatic Mathematical Logic with Logic in the broader/philosophical sense.

Unless you count logic as part of math, but I don't.

How does it feel to stand in a does-not-compute vantage point? Seriously, any CS graduate worth its CS salt knows (or should know) that the logic piece in computer science is simply axiomatic mathematical logic and set theory.

Finite State Machines? Logic Grammars? Logic Resource Contention? Logic Composite Systems? Logic Encryption? Logic and the ability to multiply and divide numbers, which is about as "math-centered" as paying your bills.

No.

Yes. Every single example you mentioned involves theory of computation (which utilizes but it is not the same as axiomatic mathematical logic) in addition to discrete mathematics, combinatorics, axiomatic set and category theories, and graph theory. Please entertain me by telling me that the last four are not branches of mathematics.

As for encryption, it is based on number theory and abstract algebra. Fields, rings, eliptic curves, that's all way above the ability of multiplication and division, serious subjects in Mathematics proper. Seriously, where did you get your CS education from?

Re:I'll be first to say WTF by logical1010 · 2011-01-20 07:22 · Score: 3, Funny

And if one of those cities is Konigsberg he'll never get it done...

--
There is something wonderful in seeing a wrong-headed majority assailed by truth. ~John Kenneth Galbraith

Re:I'll be first to say WTF by Asmodae · 2011-01-20 07:24 · Score: 3, Insightful

You probably don't have a problem with the idea that 1/3 = .333..., so multiply both sides by 3 and what do you get?

You do get 1 = 1, but you don't get 1 = 0.999... like you claim you do. By analogy with limits, the limit of an equation as x approaches y is not the same as the same equation evaluated at x = y.

Yes, yes it is. In fact that's the easiest way to calculate the limit if the function is defined at that point. It's just that functions that are defined at the limit you're looking for aren't particularly interesting. Limits get more interesting at asymptotes and infinity where you can't just plug in y into f(x).

Romanov's "algorithm" by johnwbyrd · 2011-01-20 07:52 · Score: 4, Interesting

Romanov's algorithm strongly resembles an algorithm from a debunked paper published around 2004.

Sergey Gubin wrote a series of similarly designed proofs around 2004. Instead of Romanov's notion of "concretization," Gubin used the term "depletion." Gubin's paper was debunked by some students at the University of Rochester.

Both reduction algorithms throw out key information about the original truth tables that cause the final solutions to be incorrect.

Constructive and exhaustive proofs that P != NP should never be trusted. I'm not a huge fan of formality in proofs, but sometimes you really need it.

Re:I'll be first to say WTF by Darinbob · 2011-01-20 08:02 · Score: 2

In grad school we also learned P-complete problems, the equivalent of NP-complete but for the P problem set (ie can transform any P problem to a P-complete problem in polynomial time). Those were a bitch to prove.

There is also NP-Hard. Essentially NP-complete is the intersection of NP and NP-Hard.

Re:I'll be first to say WTF by PaladinAlpha · 2011-01-20 08:16 · Score: 2

Right, and 1 exists. QED.

There is no artifact of notation, here. 0.999... is the sum of 10^-n for n of one to infinity. The limit of that expression as n approaches infinity is 1. Since the limit exists and real numbers are defined at 1, the sum of 10^-n as n goes to infinity IS 1. Therefore, 0.999... is 1.

The 0.333... * 3 = 0.999... business is mostly just a shorthand way of making that same argument.

Re:I'll be first to say WTF by Fuzzy+Eric · 2011-01-20 08:19 · Score: 4, Informative

Actually, it's unknown whether integer factorization (into primes) is an NP problem. Although a P-time solution to an NP-complete problem class (e.g. 3-SAT) would result in a P-time solution to integer factorization, the converse (polynomial time factorization implying P=NP) isn't known to hold. (And seems unlikely to be the case given the number of complexity classes that would collapse together. (ibid.))

For a long time, it was believed that even just testing an integer for primality might require super-polynomial (equiv. sub-exponential) time, which would have made the problem of just testing a candidate factor for primality not lie in P-time. But Agrawal et al. produced a P-time primality test algorithm in 2002. This result made it less clear that integer factorization into primes was necessarily not P-time. (If it were provable that testing for primality was impossible in P-time then integer factoring is not in P-time, because otherwise an integer could be tested for primality by trying to factor it and this would either return "is prime" (i.e. the trivial factorization n = 1*n) or would return "is composite" (i.e. the nontrivial factorization n = p*q) in polynomial time.) So a P-time primality test made it less clear which time complexity class integer factorization (into primes) lived in.

In spite of this nit-picking, your basic idea is right. :-)

Make your own by MrEricSir · 2011-01-20 08:31 · Score: 2

Why not create your own incomprehensible CS paper?
http://pdos.csail.mit.edu/scigen/

--
There's no -1 for "I don't get it."

Re:I'll be first to say WTF by Lobachevsky · 2011-01-20 08:33 · Score: 2

The people who think there's a non-zero "digit" after 0.0000.... need to be given the example of 12/99 = 0.1212121212... what do they think the number "ends" with, 1 or 2? Either their heads will explode trying to figure out what 0.1212121212.... ends with, or they will realize that such decimal strings do _not_ end.

Re:I'll be first to say WTF by Cinder6 · 2011-01-20 08:36 · Score: 2

Duh. There's obviously a 5 that can be added at the end of all those infinite 9s, which makes that number halfway between 0.999~ and 1.

--
If you can't convince them, convict them.

Re:I'll be first to say WTF by Cinder6 · 2011-01-20 08:41 · Score: 2

Blizzard once posted a pretty good, understandable explanation.

let x = 0.999~ (repeating)
then, 10x = 9.999~ (repeating)
thus, 10x -x = 9x = 9.999~ - 0.999~ = 9.
9x = 9, so 9x / 9 = x
9/9 = 1
x = 1, so 0.999~ = 1.

--
If you can't convince them, convict them.

Re:I'll be first to say WTF by Chapter80 · 2011-01-20 08:48 · Score: 2

um, no. 0.333... is the decimal expansion of 1/3. It just has a clumsy decimal (base-10) expansion. The ternary (base 3) expansion is quite simple: 0.1.

Or IS it that simple:
I thought the ternary expansion of decimal 1/3 was (base 3) 0.1000....

Next you're going to tell me that (base 3) 0.1 == (base 3) 0.1000....

[/silliness]

Re:I'll be first to say WTF by kbolino · 2011-01-20 09:10 · Score: 4, Informative

Let me try to address your questions in a manner that is not disrespectful.

1) The assertion that 0.999... = 1 is not equivalent to or in any way related to assertions like 0.888... = 1, which are false (why? there exists a real number between 0.888... and 1, take 0.9 for example). However, you could think of it as being related to the assertion that 0.888... = 8/9.

2) Yes, the assertion has everything to do with the infinite number of repeating digits. For comparison, the assertion that 0.999...9 = 1, where there is a finite number of 9s, is false, no matter how large that number of 9s is.

3) There are many explanations behind this infinite nature. One of the basic ones is that 0.999... is actually representing a series (infinite sum), in this case a geometric series of the form 0.9 * (0.1^0 + 0.1^1 + 0.1^2 + 0.1^3 + ...). The sum of a geometric series with ratio r is 1/(1-r), and so the sum of the series is 0.9 * 1/(1-0.1) = 0.9 * 1/0.9 = 1. I've seen some other, more elegant explanations offered here and elsewhere, but this explanation is sound and requires only knowledge of calculus (the proof of the summation formula requires limits).

4) There is no "property" that enables this assertion. Instead, this claim arises because of the disparity between the representation of numbers and the numbers themselves. Within the real numbers, 0.999... and 1 are not distinct. They appear distinct because of the decimal representation (and indeed, a representation in any base exhibits the same characteristic). This is true for all rational numbers when represented as decimals, e.g. 0.4999... = 0.5 or 0.888... = 8/9 from above.

Re:I'll be first to say WTF by Nurgled · 2011-01-20 09:37 · Score: 3, Informative

You made an error in your third line:

.5 * 10 = 5
5 - .5 = 4.5 = 9 * .5
4.5 / 9 = 0.5
0.5 = 0.5. QED.

Re:I'll be first to say WTF by didroe84 · 2011-01-20 09:47 · Score: 2

On such an epic journey he'd no doubt decide to document the experience by creating a map of all the cities he'd visited. To make it more appealing, he'd probably want to colour in the cities. Of course, it would look odd if two adjacent cities had the same colour...

Re:I'll be first to say WTF by caerwyn · 2011-01-20 10:09 · Score: 4, Informative

One of the first things I learned is that 0.333... (as an example) is an approximation of 1/3. A fraction such as 1/3 cannot be 100% accurately represented in a decimal system.

This is incorrect, and is apparently the source of most of your confusion. 1/3 = 0.333...; there's no approximation going on. 1/3 is approximated by 0.3, and 0.33, and 0.333, but the infinite decimal is *not* an approximation.

The problem here is that people are generally very ill-equipped to handle the idea of infinity, and a lot of common sense doesn't really work. You can't "tack another 5 on the end" of 0.999... to get a number halfway between 0.999... and 1, as some other poster commented, precisely because there is no end for it to be tacked onto. This is why it's ultimately equal to 1.0.

--
The ringing of the division bell has begun... -PF

Re:I'll be first to say WTF by jvonk · 2011-01-20 14:05 · Score: 2

...and because his crayons are different sizes, he wants to pack them into the smallest possible volume of his crayon-carrying knapsack.

Slashdot Mirror

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

93 of 700 comments (clear)