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

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

Comments

Probably Wrong but Clearly Falsifiable

[eldavojohn]

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!

Re:Probably Wrong but Clearly Falsifiable

[dvdkhlng]

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

[EuclideanSilence]

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

[dvdkhlng]

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:Probably Wrong but Clearly Falsifiable

[suutar]

If it's only a partial solution (implied by "failure of classification") then it's not very interesting, is it? We already have algorithms that can solve _some_ 3SAT problems, just not _all_ 3SAT problems. Wouldn't the latter be necessary to, as Romanov put it in his letter, "The fact of existence of the polynomial algorithm for 3-SAT problem leads to a conclusion that P=NP."?

Re:Probably Wrong but Clearly Falsifiable

[Anonymous Coward]

The way I see it, the graph in Fig. 2. Hyperstructures can be arbitratily complex in general case, in fact exponential.

The criss-cross at the top, bc=01, a={0,1}, d={0,1} could potentially occur 2^(n/C) times.

btw. the paper itself doesn't state P==NP or anything like this, it's only the comment of some other dude (not the author) who posted it on arxiv. and a smartass who posted it here.

Re:Probably Wrong but Clearly Falsifiable

[1 New Orleanian]

Where could I read about the details of the points you raise in your post?

Re:Probably Wrong but Clearly Falsifiable

[dvdkhlng]

I don't have any specific sources, other than the original paper linked by TFA. For my statements about using trellis algorithm, try any books about coding theory. Unfortunately the wikipedia article on trellis is not very helpful.

The more general idea behind this is dynamic programming. If you have an equation of N boolean variables, you can brute force in 2^N. If you have M equations of 2^N variables, where equation share variables only with one or more neighbouring equations, you can determine solutions for every equation on its own in M*2^N steps and save those (partial) solutions. Then to find a solution that satifies all equations you just have to find a "path" through all equations from left to right. That path has M*2^N nodes. The edges of the graph connect solutions that do not collide (i.e. where variables overlapping between solutions take the same value). Since only neighbouring equations overlap in their variables, the number of edges per node is some (not too large) constant. Finding such a path is now straight-forward and polynomial effort. see also here.

So for the riplets in this paper N is 3, so 2^N is a constant, leaving no exponential in the computational cost function. I hoped other people could comment on their impression of the paper, but as this is /. RTFA is not so common I guess :)

Re:Probably Wrong but Clearly Falsifiable

[chgros]

In fact it does suffice to show that the algorithm determines satisfiability of a 3-SAT instance in polynomial time.
Really? I have an algorithm that can solve a 3-SAT instance in constant time.
Algorithm:
if(problem == "true") then "satisfiable" else "failure of classification"
"true" is a 3-SAT instance with no variables

Re:Probably Wrong but Clearly Falsifiable

[dvdkhlng]

Playing games with ambiguity of the language I used? English grammar "a" is an indefinite article, hinting at a generic statement. Also if you look at the full post you might find sufficient redundancy to resolve any ambiguities.

Re:Probably Wrong but Clearly Falsifiable

[chgros]

Playing games with ambiguity of the language I used?
Not exactly. I was using the same language that the OP used, proving his point that the claim didn't imply P = NP. Also, in maths, "a" usually means "at least one", not "all".

Re:I'll be first to say WTF

[The MAZZTer]

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

Re:I'll be first to say WTF

[ColdWetDog]

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?

What, exactly, is 3-SAT?

[gman003]

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?

[characterZer0]

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?

[Anonymous Coward]

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?

[Anonymous Coward]

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

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

Did you check the simple wiki?

http://simple.wikipedia.org/wiki/Boolean_satisfiability_problem

Re:What, exactly, is 3-SAT?

[emt377]

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?

[token0]

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?

[debrain]

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?

[bluefoxlucid]

http://simple.wikipedia.org/wiki/Boolean_satisfiability_problem

Re:What, exactly, is 3-SAT?

[cpghost]

There's indeed a 3SAT TV station. Not to be confused with the 3-SAT problem.

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

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?

[Anonymous Coward]

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.

Re:What, exactly, is 3-SAT?

[gman003]

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

Re:What, exactly, is 3-SAT?

[gman003]

Ah. Thank you.

Re:What, exactly, is 3-SAT?

[debrain]

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?

[Anonymous Coward]

Almost there, but your polynomial time notation is off a little.

Polynomial time is O(n^x), where n is the complexity. O(x^n) is exponential time, and we already know that NP complete problems can be solved in exponential time--it just takes way too long to be practical.

Also, the Travelling Salesman problem is one of the most famous and easiest to understand of the traditional NP-complete problems.

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

Basically, the 3-sat problem is finding a set of true/false states for some variables that makes the form (a || b || c)&&(!a || d || !e) resolve to true, where you can have any number of triplets OR'ed, and potentially any number of variables. Some examples are pretty trivially solvable, like the one I just posted there which is trivially solvable by saying a,b,c,d are true, and e's true/false state doesn't matter.

Generally it's considered NP hard because it takes non-polynomial time to solve an arbitrary 3-sat problem, but if you're given the answer ahead of time it takes polynomial time to confirm.

Re:What, exactly, is 3-SAT?

[sepiroth]

From the practical point of view, NP != P would imply that certain problems cannot be solved by a clever (= fast) algorithm. You would just have to go through all the options to be sure you have found the best solution. For example, to be able to tell what is the most efficient way to visit all the cities along your trip, you would have to try all combinations: from A to B to C, from A to C to B, etc. and evaluate total length of the journey each time.

Re:What, exactly, is 3-SAT?

[hawkfish]

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.

?

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

Latina facilis est!

Re:What, exactly, is 3-SAT?

[adamdoyle]

Thank you - very helpful.

Re:What, exactly, is 3-SAT?

[marcosdumay]

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.

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

I'm a fan of easy latinas.

Re:What, exactly, is 3-SAT?

[robthebloke]

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?

[martyros]

And to make it more practical: processor architects sometimes end up with big tangled messes of of logic gates to implement certain "formulas" of logic in their chips. Sometimes, the output of a big set of logic gates often seems to be FALSE for most of the inputs they try. If the output is false for *all* inputs, then they don't really need that big mess of gates at all, they can just hard-wire it to FALSE. If it has a handful of TRUE outputs (i.e., the logic can be "satisfied), then they have to keep it.

One way to test it, of course, would be to just try all possible combinations, but this is O(2^n) on the number of inputs. But no one so far (unless the guy in this story is right) has been able to make it any better than exponential.

Re:What, exactly, is 3-SAT?

[Tenek]

Romanes eunt domus.

Re:What, exactly, is 3-SAT?

[chelberg]

Fusce google quis translate Latine loquuntur. Mathematics ut omnia faciliora.

Hint: translate.google.com

Re:What, exactly, is 3-SAT?

[prionic6]

If you're so good at it, at least translate the line for us!

smartass...

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

"difficila" ??

Re:What, exactly, is 3-SAT?

[PeterBrett]

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

I know the Roman language.

I would personally translate that as "I know the Romans' language," i.e., "<The language> <of the Romans> <I know>". The Romans' language being, of course, Latin.

Re:What, exactly, is 3-SAT?

[Carewolf]

I thought the most famous NP complete problem was the travelling salesman. Simply because it is easier to explain, and layman can much easier relate to it (though bugglars might prefer the knapsack problem).

Re:What, exactly, is 3-SAT?

[gnasher719]

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.

Only because the number of possible solutions can grow exponentially. But assume there are only 100 solutions, and you have a fast algorithm for checking whether a solution exists. Check whether a solution exists with false substituted for the first variable, and whether one exists with true substituted for the first variable. Drop any cases where there is no solution, follow those with solutions further. If there are only 100 solutions you can never follow more than hundred paths, so this lets you find all solutions effectively. If you can check whether there is a solution in O (N) where N is the problem size, and there are m variables and k solutions, then you can find all solutions in O (N * m * k).

Re:What, exactly, is 3-SAT?

[debrain]

I thought the most famous NP complete problem was the travelling salesman. Simply because it is easier to explain, and layman can much easier relate to it (though bugglars might prefer the knapsack problem).

Sir –

I agree that Travelling Salesman is probably the most famous of the these problems, but as a generic problem it has been shown to be only NP Hard, and not NP Complete. That being said, variations on TSP are NP Complete, and it would have been fine to reference it as the most famous of this sort of problem.

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

that was the translation

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

I don't know latin, but I think he did translate it.

Re:What, exactly, is 3-SAT?

[Zenaku]

I'd further point out that the "ego" in the second sentence is redundant and clumsy sounding. The pronoun is unnecessary as it is implied by the first person singular conjugation of "didici." Unless he really wanted to emphasize the pronoun, as in "Latin is not difficult, I learned it in three years." In which case, wow -- sounds pretty dickish.

Re:What, exactly, is 3-SAT?

[Carewolf]

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?

[Anonymous Coward]

This has 3 points but type. Was it supposed to be funny or troll?

Though if it was intended as troll it is funny, too.

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

he did

Re:What, exactly, is 3-SAT?

[Surt]

3-sat asks a pretty simple question. Are there boolean variables (X1, X2, X3 ....) that satisfy a sequence of logical operations that look like:

        (x1 OR x2 OR x3) AND
        (x2 OR NOT x3 OR x4) AND ...

Basically always composed of 3 OR conditions (possibly including NOT operations), joined by AND conditions. The 3 ORs is what makes it '3SAT'. There is also 2SAT, etc.

What is particularly interesting about 3SAT is that the difficulty of discovering the answer has been proved to be in NP-COMPLETE. Meaning that any other NP-COMPLETE problem can be converted to a 3SAT problem. So if you can solve 3SAT, you can solve any NP-COMPLETE problem.

Re:What, exactly, is 3-SAT?

[gman003]

The emphasis on "I" was intended to be self-deprecating - if I could learn it in three years, others should easily be able to do so as well, possibly faster.

In retrospect, it could be taken as self-promoting - "It learned it in only three years". My bad.

Re:What, exactly, is 3-SAT?

[prionic6]

I did not intend to troll, but seems that people fell for it anyway...

Re:What, exactly, is 3-SAT?

[Surt]

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

Re:What, exactly, is 3-SAT?

[Surt]

3sat is traditionally written as conjunctions of disjunctions rather than the other way around.

Re:What, exactly, is 3-SAT?

[Darinbob]

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:What, exactly, is 3-SAT?

[suomynonAyletamitlU]

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

When you go into domain-specific details, it's not "layman" anymore.

I take from your reading that satisfiability means taking a problem made out of a whole bunch of restrictions and finding out what, if anything, can possibly satisfy all of them. Mathematicians have boiled down the entire category to one, much narrower class of problems, and that's 3-SAT.

Further, if they can solve 3-SAT in polynomial time (as opposed to exponential, or anything else that gets super-complicated super-fast), they can solve all of those problems in polynomial time, which is (I am to assume, not remembering myself) all of NP-complete. That puts all of NP-complete into P, the set of problems solvable in polynomial time. Doing so successfully would put to rest a very long argument on the subject, and the algorithm that successfully does so would presumably be of great use to all kinds of people.

Re:What, exactly, is 3-SAT?

[admiralh]

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.

Not quite. Problems in the set P mean they are solvable in polynomial time O(mn^c), where n is the size of the input and m and c are constants. m and n do not increase with the complexity of the input. They have a constant upper bound regardless of input size or complexity. If your m or n is increasing, you may be hiding an exponential term (c^n) within that function.

Re:What, exactly, is 3-SAT?

[Zenaku]

Ah. My bad too. I see now that the emphasis could go either way.

Re:What, exactly, is 3-SAT?

[Joe Snipe]

Quae vox dictum latine profunda nimis.

Re:What, exactly, is 3-SAT?

[Chapter80]

Not to nit-pick.... I'm just trying to understand:

if you solve one NP complete problem in polynomial time ... you solve them all in polynomial time.

Do you mean you CAN solve them all in polynomial time? or that you DO solve them all in polynomial time?

Are you saying that this guy who supposedly solved 3-SAT solved a bunch of problems all at once?

Re:What, exactly, is 3-SAT?

[gman003]

If the polynomial-time solution of 3-SAT is correct, then he has proven that there exists a way to solve any NP-complete problem in polynomial time. The solution could probably be adapted to at least some of the NP problems, but probably not all.

Re:What, exactly, is 3-SAT?

[johanatan]

You're joking right? His statement was the translation.

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

Okay now my question is how or why is this question even useful to anyone that they would want it solved in the first place?

Re:What, exactly, is 3-SAT?

[Raenex]

Given a set of clauses that "or" a set of literals

You are talking about literals when the problem concerns variables. In fact, you seem to go out of your way, in a rather tortured manner, to not use the word variable, but do you really think somebody who doesn't know what a variable is will be helped by talking about literals?

I think you can assume that somebody on Slashdot digging into P = NP? knows the basics of boolean algebra. If not, I'm sure your explanation didn't make sense anyways.

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

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

lingua tribus annis docta, Latinam multum melius cognoscere debes! Latinam tamen certe scis tam bene ut Biblia Judaeo-Christiana legas; sed alii libri modo difficiliores sunt.

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

difficilis

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

Romanes ite ad patriam.

Eunt is "they go" when you say it as a fact, not as an order. And the phrase "go home" should not be translated literally.
Oh and "domus" is the nominative of the noun but is not the subject of this sentence.

Re:What, exactly, is 3-SAT?

[jstomel]

I dunno. If CS people think that's what the big-O is then it explains a lot.

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

3 Years so what? God made the earth in 6 days.

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

Uhm ... he is a smartass ... but he DID translate the above line :-) ...

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

He did.

Re:What, exactly, is 3-SAT?

[sourcerror]

It means people called Romanes go to the house.

Re:What, exactly, is 3-SAT?

[kylemonger]

No, a poly time 3-SAT solution would be applicable to all NP problems.

The fact that the guy posted the code is proof to me that he doesn't really have the solution. A constructive proof that P=NP is basically a license to print money; a vast array of problems would fall to dust. No one smart enough to find the proof would be stupid enough to give it away.

Re:What, exactly, is 3-SAT?

[gman003]

You're discounting altruism. Maybe the man believes that exploiting this knowledge that way would be evil, or at least unethical, and that the best action he could take is to make the code public.

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

I get it. I get that he gets it.

Still, this made me wonder how to spell 'whoosh' in latin...

Re:What, exactly, is 3-SAT?

[dkleinsc]

People called "Romanes" they go the house?

Re:What, exactly, is 3-SAT?

[kylemonger]

Given how easy inductive reasoning systems would be to develop if P=NP (always assuming tractable polynomial degree), I think I would have sat down and developed an AI first and posed the question on how to proceed to IT, rather than post the solution to the world and watch the power-hungry use it to create weapons to kill or enslave us all. I don't think you'd like the world we'd be forced to live in if P=NP and everyone knew it. Google "a personal view of average-case complexity" and read Impagliazzo's paper, particular section 2.1. It would be an algorithmic wonderland, but a nightmare for everything but machines.

Re:What, exactly, is 3-SAT?

[bhcompy]

Evidently Mr. gman's an educated man. Now I really hate him.

Re:What, exactly, is 3-SAT?

[gman003]

"Oderint dum metuant."

So, then, do you at least fear me?

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

That's exactly what he did.

Re:What, exactly, is 3-SAT?

[psmears]

Linguam romanae scio.

You know a Roman woman's tongue? I'm not sure we wanted to know that ;-)

Perhaps you meant "linguam Romanam" (the Roman language)? Or "linguam Romanorum" (language of the Romans)? Or "linguam Romae" (language of Rome)?

Re:What, exactly, is 3-SAT?

[debrain]

Where a variable such as as 'm' varies on input complexity it presumably does so linearly, in which case O(m * n^c) asymptotically approaches a * n^(c+1); i.e. is O( n^(c+1) ). O(n^5) in Vlad's case.

I reference 'm' separately as a linear coefficient directly from Vlad's paper; please feel free to take up the issue with him if you wish, or let me know if I've mischaracterized his complexity analysis.

Re:What, exactly, is 3-SAT?

[T.E.D.]

OK. Here's a problem. Clearly a *whoosh* applies here somewhere, either to the parent, or to most of my sibling posts. But it is not clear which.

Is there an algorithm to solve this problem in polynomial time? If so, does this show that P=NP?

Re:What, exactly, is 3-SAT?

[Anonymous Coward]

You're hilarious.

Re:What, exactly, is 3-SAT?

[j00r0m4nc3r]

ANDs can be converted to ORs which would make them logically equivalent

Re:What, exactly, is 3-SAT?

[kylemonger]

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

It would likely be sad for all of us, unfortunately. P=NP would be a stupendous and likely world wrecking result. I hope that if anyone ever finds a constructive proof, they'll have the good sense to withhold it until the world seems ready to deal with the repercussions.

Re:I'll be first to say WTF

[Imagix]

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

[bersl2]

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

[watermark]

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:P=NP

[mark-t]

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

Re:I'll be first to say WTF

[TheRaven64]

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:P=NP

[DoofusOfDeath]

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

Re:I'll be first to say WTF

[Anonymous Coward]

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:P=NP

[DoofusOfDeath]

Damn HTML. Let me try this in Fortran instead:

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

Re:I'll be first to say WTF

[sourcerror]

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

Re:I'll be first to say WTF

[Migala77]

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:P=NP

[Anonymous Coward]

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

[Anonymous Coward]

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

Re:I'll be first to say WTF

[Anonymous Coward]

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

Re:P=NP

[sqlrob]

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

Re:P=NP

[Anonymous Coward]

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

Re:P=NP

[Migala77]

P=NP IFF N is equal to 1. QED

Next problem?

or P=0

Re:I'll be first to say WTF

[emurphy42]

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

[Anonymous Coward]

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

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

encryption

[danlip]

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

[emurphy42]

Obligatory xkcd link

Re:encryption

[pavon]

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

[mr exploiter]

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

[TheL0ser]

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

[currently_awake]

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.

Re:encryption

[Anonymous Coward]

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

Re:encryption

[Anonymous Coward]

What would prevent using NP-hard problems for encryption?

Re:encryption

[Qubit]

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

Yeah, like the energy bill for that supercomputer. Don't even get me started on the carbon credits you'll need to purchase...

Re:encryption

[Anonymous Coward]

Even if a algorithm is polynomial, it can still be too slow. Polynomial growth means O(n^c) where c is a constant. If c = 100K, then this algorithm is too slow to have any effect on encryption in our lifetime.

Re:encryption

[vadim_t]

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

[serviscope_minor]

I thought integer factorisation (the decision version) was thought to be outside NP, so a fact algorithm for NP complete problems wouldn't help.

Can someone who knows what they're talking about weight in?

Re:encryption

[medv4380]

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.

Isn't that what the Enigma did and that was broken by Colossus Mark 1 though only 25% of the time since the Pad changed daily. It requires the users to of the Pad to be very diligent in using the pad correctly otherwise the security will be compromised. A really secure encryption is what the US used with the Navajo language. Get a group of people who know an undocumented language and then change the definition of all the words so only that small group actually knows the real meaning of the words. It would take a linguist a long time to figure out they swapped the Navajo word for Potato for Grenade and with no documentation to work from to boot.

Re:encryption

[m50d]

The impact of allied codebreaking during WW2 is vastly overestimated. During the most intense parts of the battle of the atlantic in 1941 and 42, we couldn't actually break the naval enigma, the most relevant one. It didn't change the eventual outcome.

Re:encryption

[Chowderbags]

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

[Shimmer]

This makes sense to me - it's all about the actual exponents and coefficients. Even if the exponents in the first term are the same, the coefficents might make a big difference (e.g. 100*n^3 grows 100 times faster than n^3 alone). And even if the entire first term is the same, the exponents/coefficients on the second term might come into play.

If P=NP, it means that there is a POSSIBILITY that MAYBE someone can come up with a code-breaking algorithm that is fast enough to start an arms race with code-makers. It doesn't mean that encryption as we know it is suddenly broken.

Re:encryption

[Anonymous Coward]

I think Admiral Yamamoto might beg to differ.

Re:encryption

[jd]

Less practical, but this one should be just fine

Re:encryption

[Anonymous Coward]

No, this will make _asymmetric_ encryption much less practical. The asymmetric encryption relies on the fact the you can basically distribute your key because making the key usable requires solving an NP complete problem that should take _years_. Symmetric key encryption relies on people simply not having your key to begin with*. P==NP would have the particularly nasty effect of making cryptographic signatures not work anymore, but solidly encrypting communications would still be possible.

* http://en.wikipedia.org/wiki/Diffie-Hellman_key_exchange is one example of how this can work

Re:encryption

[magarity]

I think Admiral Yamamoto might beg to differ.

Congrats; Your placement of Admiral Yamamoto using a German naval Enigma machine in the Battle of the Atlantic is the most non sequitur comment this week on /.

Re:encryption

[spammeister]

Somehow (clicked the random button), I (think I) found an even more obligatory xkcd link http://xkcd.com/287/

Re:encryption

[Hatta]

Don't worry. We will always have one time pads.

Re:encryption

[corbettw]

You do realize that Yamamoto was successfully assassinated because the US Navy was able to read all of the Imperial Navy's message traffic and knew exactly where and when to find him, right? So in that sense, our code breaking had a very large (and personal) impact on him.

Re:encryption

[chelberg]

If you are a criminal:

Plan 1: Hack into google cloud or some other easier to hack supercomputer, or your own botnet, use that to crack credit card or bank security ==> Free money!

Plan 2: Use cheap cloud computing as your own supercomputer. If you can get $1000s for $1s it is a win for a criminal.

I know of someone who has already used cloud computing to crack wireless security for about $1 just as a proof of concept.
Computing as a commodity is here, and decreasing in price, and available to all.

Re:encryption

[dsrg]

Obligatory Charles Stross link

Re:encryption

[slater.jay]

Yes, but the fact that the US was reading Japanese diplomatic message traffic effectively at will before the Pacific War even began and naval message traffic in early 1942 was certainly helpful. At Midway Nimitz had a date of attack to within one day and a complete order of battle for the opposing force, and the sinking of the Yamato was preceded by the US intercepting and decoding radio messages which pretty much exactly described what Yamato was going to be doing.

Re:encryption

[kylemonger]

The decision problem "is there a factor of n larger than m" is clearly in NP because a "yes" answer (the factor) can be checked in polynomial time (using division). However, factoring is not believed to be NP-complete, which is another way of saying that factoring is not considered to be the hardest type of NP problem. Since 3-SAT is NP-complete, a polynomial time solution to it would also be applicable to factoring. I.e. factoring decision problem can be converted into a 3-SAT instance, and then the 3-SAT solver would produce the result.

Re:encryption

[Gruturo]

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

Yeah, like the energy bill for that supercomputer. Don't even get me started on the carbon credits you'll need to purchase...

no problem!

Re:encryption

[Anonymous Coward]

POSSIBILITY that MAYBE

you repeat yourself (or are referencing a Bjork song)

Re:encryption

[serviscope_minor]

Thanks!

Re:encryption

[Anonymous Coward]

Eh, what? It is well-known that the problem is in NP. It is also trivial to show this.

Here's an algorithm to solve the problem. It can be implemented with a nondeterministic Turing machine. Incidentally, this proves the problem is in NP:

Let the size of the input be N bits.

1. Generate two factors with at most N/2 + 1 bits nondeterministically. The time cost is O(N + 2) = O(n), thus it is polynomial in the size of the input.
2. Multiply the factors. This takes at most O((N/2 + 1)^2) = O(N^2) time, which is polynomial.
3. The answer to the problem for this instance is whether the result of the multiplication matches the input. Determining this requires at most O(2N) = O(N) time.

This algorithm can be easily implemented on a nondeterministic Turing machine with polynomial overhead. Thus, the problem is in NP.

Re:encryption

[rbayer]

Despite what is taught in most CS classes, constants do in fact matter. If I give you an algorithm for breaking RSA that runs in time n^(2^1000000000000000000), it's essentially useless as the the number of clock cycles to decrypt even a 2 bit key exceeds the number of nanoseconds that have passed since the beginning of the universe. My algorithm is polynomial, but who cares?

Re:encryption

[Surt]

Yeah, USB sticks are horribly inconvenient to hand out.

Re:encryption

[Surt]

You are right, here's RSA themselves on the subject:
http://www.rsa.com/rsalabs/node.asp?id=2187

Re:encryption

[Anonymous Coward]

You mixed P and NP there. The nondeterministic version of factoring; "unfactoring" or "multiplying", is quite obviously a polynomial operation;)

Re:encryption

[noidentity]

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.

A needs one-time pads totaling the same amount of data he sends and receives. If he receives new encrypted one-time pads, he needs to already have one-time pads of the same size. Thus, your scheme would work as long as he never did anything except receive new (encrypted) one-time pads. He would be able to receive them securely, though.

Re:encryption

[Anonymous Coward]

No, that is not how Enigma worked. Enigma was not a system based on one time pads, nor was it broken by Colossus, nor was it broken only 25% of the time.

And no, the Navajo type solution isn't a practical one either. It worked then, and it'll give some degree of communication security now, but it's nothing more than a standard code system, and breakable by all the cryptanalytic techniques we already know to handle those.

Re:encryption

[Anonymous Coward]

This has little impact on encryption (based on factoring), since factoring isn't NP-Hard, meaning it can't be 'transformed' easily into any of the well known NP complete problems such as 3SAT. If this is true, however, it means much of science and math research can and will be automated. I for one welcome our singularity powered AI overlords?

Re:encryption

[Anonymous Coward]

I second the comment that you really don't know what you are talking about. Not only is mr_exploiter correct in saying that even if both are polynomial, the analysis can be more difficult than the encryption/decryption, the most used encryption algorithms are based on integer factorization, which is not known to be NP complete (and is likely not NP complete). Integer factorization is probably a "harder" problem (and is proved to be at least as hard), so even if there is a polynomial algorithm for 3-SAT, there might not be one for Integer factorization.

http://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity

Re:encryption

[VortexCortex]

but won't stop people with supercomputers.

Pfffft, tell that to Daniel Dantas, whos encrypted (w/ TrueCrypt) hard drive withstood the FBI's prying eyes for over 5 years...

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

Yes, in this case you do have big problems to worry about, whether or not your secret files stay secret doesn't have to be one of them. Note: If the strength of your encryption is what protects you from even bigger problems then perhaps it's wise to not overlook encryption.

I concede that today's encryption may eventually be broken by future computers -- I take comfort in such assumptions. Unlike information lost to dead languages, the future's Setec Astronomy might be able to decode their archives of today's data -- However, today's people will have gone long since the data could have been detrimental to anyone.

Re:encryption

[adavies42]

Are there any known public-key cryptosystems that are P to encrypt and decrypt and a class provably worse than NP (EXPTIME, EXPSPACE, etc.) to brute force?

(I'm (marginally) more familiar with the question in the "oh noes quantum!!1!1" context, where it's known (IRRC) that there are NP problems outside BQP.)

Re:encryption

[danlip]

Yes, but that's unlikely. I haven't looked at this particular algorithm but the exponent constant in polynomial algorithms rarely gets above 3. If someone shows it really is n^(2^1000000000000000000) in this case then we have nothing to worry about, until then I will assume it is small.

Re:encryption

[roothog]

Your post is nonsense.

Re:encryption

[laddiebuck]

No, worse than that, the computer to break your encryption need only be as strong as the computers performing encryption OR decryption. In other words, if you want anyone without a supercomputer to be able to use your encryption, then anyone without a supercomputer can break it too.

If there's a polynomial-time way of breaking a one-way function, the encryption based on it will be worthless.

Re:encryption

[0ptix]

NP-hardness tells us something about worst case complexity. for crypto we care about average case complexity. a problem must be hard on average not just in the worst case.

Re:encryption

[St.Creed]

Gaaah, that took 3 hours out of my evening - and I needed them!!!

Oh well, thanks for the link :) That "A Colder War" story is one of the best stories I've read in the last years. Scary as hell. I read it a few months ago for the first time but it still has a punch, even if you know the ending.

Re:encryption

[magarity]

You do realize Admiral Yamamoto was not in the Atlantic and he didn't use German Enigma machines, right? You do see how the AC responding to the Battle of the Atlantic and naval Enigma machines with a comment about Yamamoto is a total non sequitur, right?

Re:encryption

[suutar]

What if he was responding to "The impact of allied codebreaking during WW2 is vastly overestimated." and ignoring the second sentence?

Re:encryption

[Anonymous Coward]

Okay, this is bad. I laughed at the correct comic before clicking the link. We might be able to stop linking to the comics altogether.

You: oblig xkcd
Me: lol

Re:encryption

[mr exploiter]

I'm not sure if you are arguing with me, but just in case, remember that the arbitrarily large constants are fixed, so my argument is still valid.

Re:encryption

[profplump]

The constants still have to be pretty big though. Let's say you're willing to spend 1 whole minute of your desktop CPU time to encrypt each HTTPS transaction with your bank. Even if it take 100,000 times longer to decrypt it, that's still only 70 CPU-days. Assuming the task can be divided to multiple processing units someone with access to even a moderate amount of computational units could have your password in under a day.

And that's with you waiting a full minute for each new connection, which is much more than is practical for everyday use.

Re:encryption

[vadim_t]

Wow, such a devastating argument!

I'll go quietly cry in a corner now.

Re:encryption

[vadim_t]

Very.

For one, we're most likely on different contients. For best security you'd want to hand it over in person.

Also sticks aren't that big. It's fine for email, but not a whole lot if you want to send DVD images.

You also need a separate OTP for every 2 people that talk to each other. One file for Alice to Bob, another for Alice to Carol, another for Bob to Carol, and so on. That gets annoying pretty fast, and to make all those OTPs in the first place you'll need one nice RNG. It's going to take quite a while getting 16GB of random data from /dev/random.

Re:encryption

[ShadowRangerRIT]

Except he wasn't arguing the specific case (Enigma), he was arguing the general case (cryptanalysis was critical to victory in WW2). Take a look at the history of the Battle of Midway, specifically the impact that Joseph Rochefort's team had. No, it didn't win the battle on its own, even with advance knowledge Nimitz was still outnumbered, but winning the battle without it would have been impossible.

Re:encryption

[Shimmer]

That is a good point. Given this, it probably does take a large difference in exponents to ensure safety. For example:

* Practical safety ratio = 1 : 10^50 (1 second of encryption time requires 10^50 seconds of decryption time)
* Encryption algorithm performance = n^2
* Decryption algorithm performance = n^10

How big does 'n' need to be before we cross the safety threshold? 10^(50/(10-2)) = 10^6.25 = 2 million. That's a large key.

Re:encryption

[Anonymous Coward]

You can choose n so that the cryptanalysis is arbitrarily more difficult than the encryption

No you can't. The factor of "more difficult" will always be n. It will always be n times more difficult.

And since your "encryption" is a process of O(n^2), "arbitrarily more difficult" (i.e. n >>> 0) basically just means you need a really powerful computer to do the encryption in the first place.

Re:encryption

[RockDoctor]

A really secure encryption is what the US used with the Navajo language.

Just as one point on that, I suspect that's more akin to an encoding than an encryption. But I'm not really enough of a math person to put that as stronger than a gut feeling.

Get a group of people who know an undocumented language

Hmmm, interesting. With something well over half of the spoken languages in the world functionally extinct, or going to become extinct shortly ... that's going to be such a trivial problem. For the documented languages, a large part of that language diversity is in Papua new Guinea.

I'm sure that's going to help your nations communications needs.

For my nation's communication needs, then there's a tiny problem that the gap between the native speakers of the country's three languages and the total population is approximately zero. It's possible that there are the thousands of unregistered people in your country who could service your country's needs ... but wouldn't they be, almost by definition, those filthy terrorist scumballs who don't register their children with the authorities.

Has your country been successful at preventing all native Navajo speaker from exiting the country, or teaching filthy foreign scumballs the language? Yeah. Scales well. High security. Can't speak too highly for it. You should be on the ... ummm ... Presidential Security Advisory Commission, or something like that.

Re:encryption

[Zeroko]

The paper claims the algorithm is O(n^4*m), where n is the number of variables & m is the number of clauses, & for interesting instances m > n, so it is pretty slow.

Re:encryption

[mr exploiter]

So what, I can choose n, so my comment is still true. Besides that, this is just an example that polynomial cryptanalysis doesn't imply practical. That would depend on the actual polynomial.

Re:I'll be first to say WTF

[bluefoxlucid]

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:P=NP

[Anonymous Coward]

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

Re:I'll be first to say WTF

[Noughmad]

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

Re:P=NP

[Anonymous Coward]

Stop reinforcing the stereotype that math geeks have no humor.

Re:I'll be first to say WTF

[HarrySquatter]

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

You mean except RSA?

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

[Anonymous Coward]

"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

Re:P=NP

[kwerle]

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.

Simple Explanation

[Haedrian]

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

[Anonymous Coward]

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

Re:Simple Explanation

[somersault]

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:Simple Explanation

[Haedrian]

The notation you want is

O(e^n) since its exponential.

O(N^2) is perfectly feasible - the basic search algorithm is done in N^2 (since you pass the set of terms twice).

"Small sets" needs to be very small. Even 100 is an essageration

Re:Simple Explanation

[Haedrian]

Sorry, I meant 'the basic SORTING' algorithm. Search is N time.

Re:Simple Explanation

[somersault]

Hmm okay. N^2 is still exponential, but obviously not as bad as e^n!

Re:Simple Explanation

[Haedrian]

Nope, that's polynomial

N^naturalNumber is a polynomial (remember Math class?)

Its not an exponential increase - and its not anything as bad as an exponent

To demonstrate:

n = 1000

O(N) = 1000
O(N^2) = 1000000
O(2^N) = 1.07 * 10^301

Re:Simple Explanation

[somersault]

Ah. I do remember polynomials, but it has been 10 years since I've taken a Maths class, and somehow I thought that if a curve's slope was becoming sharper that it was exponential. *facepalm* At least I'm still able to optimise my code in practice :p

Re:Simple Explanation

[somersault]

PS - thanks for being so helpful! I'm often loathe to (purposefully) admit ignorance on Slashdot as there are a lot of douches around, but it's posters like yourself that make /. worthwhile :)

Re:P=NP

[Haedrian]

P and NP are sets...

Re:I'll be first to say WTF

[HarrySquatter]

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

[Anonymous Coward]

"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

[mark-t]

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

[morgan_greywolf]

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:P=NP

[eggnoglatte]

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

Interesting

[Anonymous Coward]

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

[Anonymous Coward]

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!

Re:I'll be first to say WTF

[Anonymous Coward]

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

[vux984]

"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:P=NP

[Anonymous Coward]

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:I'll be first to say WTF

[KublaiKhan]

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

[skeptikos]

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

[dch24]

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:P=NP

[mark-t]

Okay... fair enough...

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

Goldbach Conjecture

[Bazman]

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

Re:Goldbach Conjecture

[I8TheWorm]

I just spent my last mod point about an hour ago... so +1 Funny if no other mod gets it.

Re:Goldbach Conjecture

[Darinbob]

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

Re:Goldbach Conjecture

[JamesP]

You might try to optimize your solution with something called "an infinite loop" look it up

Re:Goldbach Conjecture

[tepples]

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

That's what torrents are for.

Re:Nice way to spread malware?

[Haedrian]

. . .

"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

[dch24]

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.

Maybe 3-SAT isn't NP-complete

[Thundersnatch]

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

[Haedrian]

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

[Anonymous Coward]

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:Maybe 3-SAT isn't NP-complete

[Thundersnatch]

Right, but I haven't read (and probably could no longer understand now that I am 15 years out from my CS degree) the proof that 3-SAT was NP at all to begin with. Did Levin and Cook assume that 3-SAT was NP based on some prior work? Could that proof have been in error?

Re:Maybe 3-SAT isn't NP-complete

[deapbluesea]

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"

Unfortunately, the author of this paper has claimed that his algorithm is P simply using the 8-ball proof. There's no turing reduction of 3-SAT to his method, no soundness or completeness proof on his algorithm, and no algorithmic analysis other than "I ran it many times". The likelihood of this claim being false is astronomically higher than the likelihood that 3-SAT was proven to be NP-Complete (esp since they make us rework and understand the proof to get a higher level degree in CS)

Re:Maybe 3-SAT isn't NP-complete

[Anonymous Coward]

3-SAT is NP-Complete because Levin and Cook proved that you can reduce any problem in NP to the 3-SAT problem in polynomial time. The argument that 3-SAT isn't really in NP is the exact argument used to prove that P=NP. Showing that there is a polynomial time algorithm for 3-SAT is the only way to prove that P=NP that we know of.

After reading other comments, however, it appears that this paper is based only off of a statistical test of several problem sets. That doesn't let you measure actual big-O values, for the same reason that quicksort is, technically, a O(n^2) operation. Just because there are problems that work nicely doesn't mean that all problems will, and if even one problem exists that requires exponential time (or can't be solved by this algorithm), then he hasn't proved that P=NP.

Re:Maybe 3-SAT isn't NP-complete

[Anonymous Coward]

Disclaimer: I'm not the grandparent AC, and I disagree with him/her that 3-SAT was the first (see below).

The fact that k-SAT is in NP is trivial -- just find a satisfying input and test it in linear time.

The original idea of NP completeness came from Cook's proof that general k-SAT is NP complete. The proof is based on thorough analysis of the memory states of a hypothetical Nondeterministic Turing Machine (NTM). It shows that any boolean problem that can be evaluated on an NTM in polynomial time can be expressed as a k-SAT problem. Therefore k-SAT is "complete" for problems solvable in polynomial time on an NTM (i.e. the complexity class NP).

After Cook's proof, mathematicians quickly discovered a linear transformation from k-SAT to 3-SAT, which means that any 3-SAT solver can easily solve k-SAT. This is an example of a polynomial time (linear in this case) reduction from an NP complete problem to another problem in NP, and it's the basis that we use to establish NP completeness. Almost all other problems in NP have been proven by polynomial time reduction from 3-SAT to the problem in question.

Re:Maybe 3-SAT isn't NP-complete

[marcosdumay]

The one problem that all other are deduced from is SAT. 3-SAT is a friendlier version of it, that was proved to be NP-Complete by mapping SAT into it.

But, yeah, most people try to map 3-SAT into their problems before trying with SAT. That is because 3-SAT is easier to think about, and somebody already proved it is NP-Complete.

And, by the way, there are bare proofs about NP-Completeness of other problems, without reducing them. People don't like to use them because they are messier than simply mapping 3-SAT into your problem.

Re:Maybe 3-SAT isn't NP-complete

[rbayer]

The proof is actually rather technical, but the general idea is as follows:

A problem is in NP iff solutions to said problem can be verified in polynomial time. That is, there is a Turing Machine that when given an instance of the problem and a proposed solution will run in polynomial time and spit out a yes or no; we'll call this machine the Verifier.

Since we are trying to show that solving 3-SAT in poly time solves any NP problem in poly time, let's start by picking any old NP problem, and call it's verifier machine V. Let's also pick some particular instance of the problem that we're interested in. To answer our question, we essentially need to answer the question "Is there any input to V that will cause it to give a 'yes'". The hugely technical part of the Cook-Levin theorem is that the preceding sentence can actually be coded as an instance of 3-SAT with polynomial-many (in the length of your problem instance) clauses; this is done by introducing variables to trace each step of the computation of V to make sure it agrees with what V is supposed to do and then having extra variables for the inputs of the proposed solution. Thus, if you can answer this 3-SAT problem in polynomial time (as you surely can if you claim to have an algorithm that can answer ANY 3-SAT problem in poly-time), then you have answered the original question from your other NP problem in poly time as well.

Re:Maybe 3-SAT isn't NP-complete

[Anonymous Coward]

3-SAT is not the easiest way to redefine NP-complete, actually simple SAT (satisfiability of a logical formula) is much easier. An NP-complete problem just means the problem is NP and all NP problems can be poly-time reduced to it. What makes SAT so appealing for this is the fact that you can put a Turing Machine's halting condition in terms of pure logic (granted with tons of variables and clauses). Therefore, you can effectively "simulate" the Turing Machine with logic, and thus state is as a SAT problem. Therefore SAT is NP-complete, and by chaining poly-time reductions, if you can reduce problem X to SAT, then X is NP-complete.

Re:Maybe 3-SAT isn't NP-complete

[Anonymous Coward]

Well, you can reduce 3-SAT into an instance of 3-SAT in polynomial time, so i guess it's NP-Complete.

Re:Maybe 3-SAT isn't NP-complete

[mparker762]

No. It's certainly possible for some random problem to be misclassified as NP-complete because of a botched reduction proof. This sort of mistake has happened before, and it's not a big deal for anybody but the poor student. But 3-SAT is special - it was the first NP-complete problem that was discovered; the proofs of the other members of NP-complete depends on 3-SAT being in NP-complete. So if 3-SAT is in P then either all the reduction proofs for all the other NP-complete algorithms are wrong (very unlikely), or P==NP.

Re:Maybe 3-SAT isn't NP-complete

[Anonymous Coward]

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?

Cook's Theorem says that any problem, say Q, that's in NP (and P is a subset of NP) can be transformed (aka, reduced) into an instance of Boolean Satisfiability (SAT, not necessarily 3-SAT; although of course SAT can then be further transformed into 3-SAT, etc.) in an amount of time that's a polynomial of Q's input size.

This means that if we can solve SAT (or, equivalently, 3-SAT) in a polynomial time, then we have the overall procedure of:

- Take any NP problem Q and transform Q into SAT (in polynomial time)
- Solve the new SAT problem in polynomial time
- ...and we have an answer for Q in polynomial time, since a polynomial + a polynomial is a polynomial.

---

The gist of the first transformation (which Cook uses to initially show SAT's NP-completeness) is to encode the state-configurations of the Turing Machine that's solving Q with Boolean variables (i.e. list all of the possibilities of "Is the Turing Machine in *this* state, with *this* data, at *this* time?" -- the trick, of course, is in showing that there are not too many of those; that the number required is itself polynomial). If the Boolean formula is satisfiable, then its satisfying assignment represents a satisfying computation for Q.

Re:Maybe 3-SAT isn't NP-complete

[Anonymous Coward]

Well, hold on a second. There actually isn't actually anything special about 3-SAT. Every NP-complete can be polynomial-time reduced to any other NP-complete problem, making them basically "equivalent." So you can use any NP-complete problem you want to define the class NP-complete. Textbooks often reference satisfiability (SAT) when defining NP-completeness, but that is for historical reasons. It's also true that NP-completeness proofs often use 3-SAT reductions because 3-SAT is well suited to the kinds of reductions those proofs use.

Furthermore, it is possible to define NP-completeness without referencing any specific problem, so there are critera for NP-completeness that are in a sense more "fundamental" than the existence of a 3-SAT reduction.

That means that if 3-SAT turns out to not be NP-complete, it doesn't invalidate the notion of NP-completeness. I can't immediately dismiss Thundersnatch's idea that P!=NP but the proof of 3-SAT's NP-completeness is mistaken. There could still be other problems that are actually NP-complete, but it would mean we would no longer have NP-completeness proofs for a lot of problems that are understood to be NP-complete (though they still may be NP-complete).

It's extremely unlikely (the proof of 3-SAT's NP-completeness is pretty well understood), but it's a cool idea and a good way of looking at the problem.

Re:Maybe 3-SAT isn't NP-complete

[Seth024]

I believe it was based on the NP-completeness of the general SAT.

1) 3SAT is a special case of SAT so it's also NP.
2) A SAT problem can be reduced to 3SAT (add some variables to it: x||y becomes x||y||z && x||y||NOTz (similar for clauses with 1, 4, 5, 6... numbers of literals)
3) the reduction is clearly done in polynomial time

Re:I'll be first to say WTF

[Anonymous Coward]

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

Re:I'll be first to say WTF

[spud603]

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.

Intel and AMD both hope P!=NP

[Algorithmnast]

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.

Re:Intel and AMD both hope P!=NP

[serviscope_minor]

Yes, because fabricating with 20nm lithography is certainly an NP complete problem. I really don't know much about complexity classes, but I know that lithography isn't in there.

Re:Intel and AMD both hope P!=NP

[marcosdumay]

Yep, that is very important. If P=NP chip designing becomes a solved problem. Fabs are actualy more expensive than 10mil, but anybody can contract them...

In a related news, expect all cars and planes to change into the optimal aerodynamics shape in no time.

Re:Intel and AMD both hope P!=NP

[rlwhite]

It's a joke referencing transistor types: http://en.wikipedia.org/wiki/P-n-p_transistor

Re:Intel and AMD both hope P!=NP

[Carewolf]

I thought he refered to the layout problem. Laying out the components in a CPU in the most optimal fashion is a wellknown NP-complete problem. This doesn't solve getting the best manufacturing plants of course, but it would make it much easier for someone with a good design to turn it into an efficient design that is able to compete with companies that has decades of experience into making good designs.

Re:Intel and AMD both hope P!=NP

[Anonymous Coward]

Routing the lines between the different sections of CPU is NP complete, I think?

Re:Intel and AMD both hope P!=NP

[Algorithmnast]

Yes. Exactly.

Re:Intel and AMD both hope P!=NP

[Anonymous Coward]

I believe that the point Algorithmnast was making is that the security of Intel's and AMD's internal chip layout strategies is solely based on asymmetric key encryption, and if P == NP, then that security can be broken, because prime factorization will theoretically be possible in polynomial time.

Never mind that they probably have more layers of security than a single public/private key pair.

Re:Intel and AMD both hope P!=NP

[treeves]

$10MM is cheap for a single state-of-the-art ArF immersion scanner. A fab? Try $ billions for a real sweet one.

Re:I'll be first to say WTF

[morgan_greywolf]

Much better car analogy. Thank you. :)

Re:I'll be first to say WTF

[UnknowingFool]

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.

Re:I'll be first to say WTF

[Anonymous Coward]

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

[morgan_greywolf]

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

Re:I'll be first to say WTF

[abigor]

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

[TheCycoONE]

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

[jandrese]

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

Yes. Any other questions?

Re:I'll be first to say WTF

[TheRaven64]

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

[Anonymous Coward]

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

[Qubit]

what does P stand for?

Portman.

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

Re:P=NP

[Anonymous Coward]

Or P=0 and N=anything.

Therefore you fail alegbra.

QED

Interesting...

[shadowrat]

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

[corbettw]

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.

Re:Interesting...

[Anonymous Coward]

While those who actually understand proofs of computational complexity are mostly really brilliant people, the mere fact that one doesn't understand it doesn't imply anything.

The people who do get it, are those who spent significant time into learning very domain specific knowledge.

Re:Interesting...

[StikyPad]

Articles like this remind me of my true status, which is helpful in not getting cocky.

It would be humbling, yes, if it were not indicative of just how stupid most people are.

Re:Interesting...

[treeves]

I'm pretty sure you could be of above average intelligence and still fail to understand this proof. Contemporary mathematics is, as I understand it, of such a nature that even mathematicians can't understand proofs in areas outside their own particular field. (At least I hope that is the case)

Re:Interesting...

[Arterion]

It's probably not that you aren't smart, just that it's a complicated subject requiring a lot of otherwise pointless knowledge that can be rather grueling and tedious to learn.

Think about a second language. A lot of rather dumb people can speak two languages. Yet even a genius just understand another tongue without spending a good bit of time learning it first.

Re:Interesting...

[claytongulick]

As well as doing what you mentioned, the article has also inspired me to work on learning more math.

Re:I'll be first to say WTF

[Zediker]

Polynomial time (P) or Nondeterministic Polynomial time (NP)

Re:I'll be first to say WTF

[deapbluesea]

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.

Re:I'll be first to say WTF

[kiwix]

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:P=NP

[Anonymous Coward]

https://secure.wikimedia.org/wikipedia/en/wiki/Nondeterministic_Turing_machine#Comparison_with_quantum_computers

Re:I'll be first to say WTF

[deapbluesea]

I believe the burden of proving this correct rests with the author of the paper. I have read his paper, and he has not proven that his algorithm is polynomial, nor has he proven that his algorithm is a sound and complete reduction from 3-SAT. There's no need to say he's wrong, only that he certainly hasn't proven himself to be right.

Re:I'll be first to say WTF

[Zediker]

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

Who needs the Bible Code? OMG its 42!

[vajrabum]

I think God might be sending us a low bandwidth message via P=NP and P=!NP papers. The message can theoretically be extracted by assigning 1 to P=NP and 0 to P=!NP then arranging the bits in the chronological order of the papers (or maybe that should it be 0 to P=NP and 1 P=!NP). The problem is that you can't find "papers" and tech reports which have disappeared down the memory hole and lots of the nutjobs won't have put dates on their offerings. http://www.archive.org/ to the rescue!

Math always a part of CS ...

[perpenso]

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.

Math has always been a big part of CS. Early CS degrees tended to be a specialized math degree and some CS programs were still under the math department in the 1970s (some in the 80s?) as opposed to CS being its own full fledged department.

Re:Math always a part of CS ...

[chelberg]

I know of CS programs still in the Math department today, also some in the college of business. Here at Ohio University in 1996 CS moved from Arts and Sciences to Engineering. At the time, the degree was very much still aligned to Math which it grew out of. Our university is now moving to semesters, and as part of the curriculum redesign we have moved to a curriculum much more like engineering than A&S. We still have a large math component. It is possible for our students to get a minor in math with just a couple of more math classes than we require for CS.

Re:I'll be first to say WTF

[amRadioHed]

One-time pads will always be strong encryption, but they are impractical to the point of uselessness for the vast majority of our uses.

Re:P=NP

[undecim]

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.

Re:I'll be first to say WTF

[Zediker]

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

Re:I'll be first to say WTF

[Anonymous Coward]

Well, it will be pretty much like it is now but with even more people who are completly clueless when it comes to small microcontrollers and electronics.

Re:I'll be first to say WTF

[Zediker]

doh, posted in wrong spot =(

Re:I'll be first to say WTF

[H0p313ss]

might have an impact on many things that geeks care about.

True, but it's equally fair to say:

• It may have NO impact on things that geeks care about
• It may have impact on things NO geeks care about

That bit of pedant-ism aside it is basic CS, if you think you know anything about computers you should be aware of algorithms and the P!=NP debate. You don't have to care, but you do have to know. Just in the same way you have to be aware of basic atmospheric chemistry, the greenhouse effect and grade 9 biology to have an opinion about the effect of changes to the concentration of atmospheric CO2 on global temperatures.

The number of so called "software-engineers" who have inserted O (n^2) code into my projects makes me weep.

Not a proof but a definition

[Anonymous Coward]

There can't be a proof.
A problem is in NP if you can reduce it to 3-SAT (in polynomial time).

Re:Not a proof but a definition

[Anonymous Coward]

Nope, the basic definition is based on Turing machines: a problem is in P if its solutions can be recognized in polynomial time by a deterministic Turing machine, and in NP if it can be recognized in polynomial time by a non-deterministic Turing machine. Cook's theorem demonstrates that the satisfiability problem SAT is NP-complete. Reducing 3-SAT to SAT is another proof on top that. Both proofs can be found in Garey & Johnson.

Re:I'll be first to say WTF

[slim]

Just one question.

If it's proven that P==NP, does it necessarily follow that for an arbitrary NP hard problem, an algorithm to solve it in linear time will be found?

I think P==NP implies that such an algorithm *exists*, but surely finding it is another matter?

Re:P=NP

[SuperSlacker64]

Nope, and that's why NP-complete problems are currently not calculable (at least not in the true, best case scenario, unless you get really lucky and your algorithm succeeds on an early attempt). The concept of a nondeterministic Turing machine is basically that you have a machine that as it goes along to solve the problem, can instantaneously split itself into multiple copies to try to calculate different paths along the algorithm.

If it helps, picture it like a hypothetical infinite core processor. Every time the algorithm hits a branch (if, switch, that kind of idea), rather than simply choose one of them to follow, it creates a copy of itself on another core and each copy starts going through one of the paths. On our limited and finite machines, this gets impossibly large very quickly (think lots of recursion). So if they really did prove P=NP, that's a major leap for Computer Science. But it's still hard to believe, seeing how many other people have spent so long trying.

Re:I'll be first to say WTF

[Anonymous Coward]

woosh!

Re:I'll be first to say WTF

[Anonymous Coward]

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

[geekoid]

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.

Re:I'll be first to say WTF

[Thuktun]

It's also a giant mecha.

Re:I'll be first to say WTF

[Mister Fright]

Yes, but once they have a proof it should be very easy to verify.

Re:P=NP

[Anonymous Coward]

Yes. Nondeterministic simply means you make a random decision at each branch. Just hook up a real random number generator to your PC and use it to control the branching and bam.

Re:I'll be first to say WTF

[sakonofie]

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

[geekoid]

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.

Re:I'll be first to say WTF

[Zediker]

nah, it just says that any nondeterministic problem should also have a polynomial time solution. Linear time solutions are not covered by the conjecture.

Re:I'll be first to say WTF

[marcosdumay]

I'd arguee that being a computer geek requires that you understand what the (possibly) biggest discovery about computing of the decade is.

Re:Nice way to spread malware?

[undecim]

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

Re:I'll be first to say WTF

[Zediker]

errr, i should say, any nondeterministic polynomial time problem should also have a deterministic polynomial time solution... All in all, its a very specific solution to a very specific class of problem.

Re:I'll be first to say WTF

[Anonymous Coward]

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.

This is a good intuitive description. But a more complete definition involves reductions to those hard problems. A well-formed proof should demonstrate that the encryption algorithm is HARD if and only if a fundamental problem is HARD. Those fundamental problems are typically number theoretic in nature, e.g., factoring. But there should be a demonstrable reduction in both directions to show equivalence.

As I said earlier, RSA is not equivalent to factoring. It lacks a proof from factoring to RSA. DH and the discrete log problem has an equivalence relation (reduction in both ways). And to me, that makes it stronger. Someone could find a great way to compute Euler totient functions (potentially much easier than factoring) and RSA would be weak.

Re:I'll be first to say WTF

[HarrySquatter]

Well, yes, but I wasn't attempting to be exhaustive in list.

Your Post Is Fundamentally Incorrect

[Anonymous Coward]

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.

Incorrect.

Re:Your Post Is Fundamentally Incorrect

[psmears]

Why is this incorrect? The factoring problem is in NP, so if P=NP then it is in P (which is presumably what the OP meant by "NP easy").

Re:Your Post Is Fundamentally Incorrect

[Garridan]

However, factoring is in NP, not NP-hard: both multiplication and verification of primality take polynomial time.

Re:I'll be first to say WTF

[mrstrano]

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:P=NP

[Haedrian]

I'd think it's equal to the identity set.

Re:I'll be first to say WTF

[BlueWaterBaboonFarm]

Mod parent up!

Good read.

Re:I'll be first to say WTF

[Anonymous Coward]

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

What? You do know that != means "not equal", right?

My personal wild guess

[roguegramma]

My personal wild guess is that a large number of the subproblems of an NP question will turn out to be solvable in polynomial time, but a core of "prime problems" will remain which require non-polynomial time.
I have this idea since I know of the queens problem - there are a lot of easy solutions for certain sizes of the board.

Re:My personal wild guess

[Anonymous Coward]

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.

Re:My personal wild guess

[DriedClexler]

I don't see where the GP suggested that -- he specifically said that there's a core that will always be super-polynomial, making the class as a whole superpolynomial. He only said that a "large number" of special circumstances that can be done in polynomial time but *don't* cover the whole problem class.

Re:I'll be first to say WTF

[jd]

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.

Re:I'll be first to say WTF

[H0p313ss]

Who are you the fucking geek police? Fuck you! You don't get to dictate to us which of us are and aren't geeks. Fucking asperger retard....

I hope you were aiming for irony.

Re:I'll be first to say WTF

[sakonofie]

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

[Anonymous Coward]

Factoring problem hasn't been proven NP hard. In fact, since it's both in NP and co-NP, it's suspected to be neither in P nor NP-hard (provided that the entire purported hierarchy doesn't collapse under P=NP).

Re:I'll be first to say WTF

[buchner.johannes]

here is the paper: http://arxiv.org/abs/1011.3944
Title: Non-Orthodox Combinatorial Models Based on Discordant Structures
Authors: V. F. Romanov

Re:I'll be first to say WTF

[SandFrog]

Maybe there wasn't enough space in the margin.

Re:I'll be first to say WTF

[Anonymous Coward]

probably

Re:I'll be first to say WTF

[daremonai]

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

[Anonymous Coward]

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

What? You do know that != means "not equal", right?

Precisely. "not equal" rather than "probably not equal".

Re:I'll be first to say WTF

[Anonymous Coward]

Posting anonymously to preserve mods on this thread.

Although RSA is not *equivalent* to factoring, a solution to factoring is a solution for RSA - you've got the direction wrong. If I have a factoring oracle then any RSA problem includes a modulus defined to have exactly two prime factors. If pass this modulus to the oracle then I have p,q and can thus solve the RSA problem (through standard decryption).

Re:I'll be first to say WTF

[corser]

The number of so called "software-engineers" who have inserted O (n^2) code into my projects makes me weep.

What if the code is a matrix multiplication algorithm?

Re:I'll be first to say WTF

[Anonymous Coward]

well through induction nothing is provable beyond what we have defined as axiomatic. at some level you just have to assume things.

Re:I'll be first to say WTF

[Anonymous Coward]

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

If we make a rule that we can't discuss anything someone doesn't know about, then we guarantee that no one learns anything.

I would prefer to have the opposite rule: If all I learn by reading something is someone's opinion, then it should be banned.

Re:I'll be first to say WTF

[Anonymous Coward]

RSA does not depend on P vs NP. It is currently an open question what the complexity of factoring is.

Re:I'll be first to say WTF

[Anonymous Coward]

Then Neo gives the solution in bullet-time and kicks some machine-butt before anyone notices that he got the solution from the oracle who looked up the result from the last iteration.

Re:I'll be first to say WTF

[Anonymous Coward]

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.

Factoring is *not* known to be NP hard. It is in NP, however.

It's quite possible that a fast factoring algorithm could come along, and not tell people a thing about P ?= NP.

Re:I'll be first to say WTF

[H0p313ss]

The number of so called "software-engineers" who have inserted O (n^2) code into my projects makes me weep.

What if the code is a matrix multiplication algorithm?

I'm not saying n^2 is unacceptable in all circumstances. (And I was not clear)

My problem is clueless people who would not know an algorithm if it hit them in the face not taking into consideration overall product scalability.

n^2 is ok if you know you only have a handful of inputs, however if you try to do something like filtering an email inbox with a polynomial algorithm then you're unlikely to make customers happy.

Re:I'll be first to say WTF

[dgatwood]

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

I wouldn't go that far. I would actually have said the opposite---that if a problem can be verified to be correct in polynomial time, it stands to reason that there should be a way to solve it in poly time. After all, there are hundreds of heuristic approaches that solve them for certain subsets of the problem, certain special cases, etc. All that is missing is a generalizable approach. It might be true that no way to generalize them exists, but if it is, it's the sort of right that requires extraordinary proof in my book.

I've been saying for years that I thought it would be downright hilarious if somebody proved P = NP and really messed with the heads of theoretical computer scientists, so I'm kind of hoping this pans out in a schadenfreude sort of way. That said, statistically, given how many attempts people have made to prove this one way or the other, it probably won't.

Besides, P = NP if N = 1. Everyone knows that. :-)

3-SAT not in NP-Complete?

[Anonymous Coward]

Is it possible that he just disproved that 3-SAT is in NP-Complete?

Re:3-SAT not in NP-Complete?

[Anonymous Coward]

Nope.

Re:I'll be first to say WTF

[bunratty]

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.

Am I Confused?

[quantaman]

So my understanding is that P is the set of problems both verifiable and solvable in polynomial time.

NP is the set of problems verifiable in polynomial time, but we can't currently solve in polynomial time

NP-Complete is a set of problems in NP where one can be reduced to another in polynomial time, so if you could solve one in poly time you could solve all in poly time

3-SAT is NP-Complete.

So assuming this code is correct (which sounds very unlikely), wouldn't it merely prove that NP-Complete is in P? Not to say this wouldn't be a major result, but that's not the same as the more general P==NP.

Am I misunderstanding something?

Re:Am I Confused?

[gall0ws]

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.

Re:Am I Confused?

[betterunixthanunix]

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.

Re:Am I Confused?

[sakonofie]

Your definition of NP-completeness is a bit off. An NP-complete problem is a problem that is in NP and any problem in NP can be reduced to it in polynomial time. (This eludes some technicalities, but you can look them up if you really care.) So any problem in NP can be reduced to a 3-SAT query in polynomial time. If this result is correct, any problem in NP can be reduced to 3-SAT in polynomial time, which can then be solved in polynomial time by this algorithm. This results in a polynomial time algorithm for any problem in NP. Hence NP is a subset of P, and P==NP.

Re:Am I Confused?

[iamthelaw]

Your definition of NP is not expansive enough -- NP includes P; it is the set of problems verifiable in polynomial time (period).

NP-complete problems are the hardest problems in NP -- if you can solve any of them in polynomial time, then you can solve every problem in NP in polynomial time.

Re:I'll be first to say WTF

[deapbluesea]

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.

Re:I'll be first to say WTF

[Ihmhi]

I honestly have a difficult time with some of this theoretical stuff.

For instance, the whole 0.999... = 1 thing. I think that's a load of crap. You can bring in all sorts of complex calculations, but the fundamental rules (as we're taught) say a run-on number like 0.999... goes on forever. No matter how far back you get, there's a 9 at the end. That 9 isn't going to get a 1 added to it and start a domino effect to magically make it 1.

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

Re:I'll be first to say WTF

[Anonymous Coward]

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.

"a == a" is not an axiom, it is the definition of the "==" symbol.
Axiom != definition.
  The consensus in only in that we write the symbol as "==" and not for example as "$&".

Re:I'll be first to say WTF

[Anonymous Coward]

Red flag: In the paper, he uses the hand-waving term "in parallel" (with emphasis) in the proof section when describing an algorithm involving an unbounded value "k".

Re:I'll be first to say WTF

[matunos]

Integer factorization is not believed to be in the NP-complete class.

Re:I'll be first to say WTF

[Hatta]

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

What other option is there? It's either polynomial (P) or not polynomial (NP), isn't it?

Re:I'll be first to say WTF

[I8TheWorm]

Yeouch, so all nerds who aren't math nerds are fans of Fox News? I was quietly reading and learning a bit until I saw this post.

Re:I'll be first to say WTF

[melted]

Exponential is still pretty darn hard for large powers. Easier than brute force search, but every additional bit in key length will add to the exponent, and it's awfully easy to add bits to keys, assuming your key is not already e.g. 4096 bit long.

Re:I'll be first to say WTF

[Anonymous Coward]

Check your CS terms. "NP-hard" is not code for "NP is hard". Its a different complexity class altogether. Unlike the class NP, we have no reason to believe that NP-hard problems are reducible to NP-complete. The statement "If P=NP, then NP-hard=P" is false.

Re:I'll be first to say WTF

[I8TheWorm]

Hehe, I was thinking the same thing. Unless now-a-day means "at least as early as 1989" in my case.

Re:I'll be first to say WTF

[EllisDees]

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.

 

Re:Nice way to spread malware?

[Colonel Korn]

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

Doesn't this seem like the best way to spread the Snow Crash virus?

And while I'm thinking of it, I had a realization: The Entertainment in Infinite Jest seems like a rip-off of Snow Crash in Snow Crash.

Re:I'll be first to say WTF

[Frank T. Lofaro Jr.]

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

Re:I'll be first to say WTF

[snowgirl]

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

Re:I'll be first to say WTF

[pipatron]

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.

Re:I'll be first to say WTF

[networkBoy]

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"

Re:I'll be first to say WTF

[commander_gallium]

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

[TwilightXaos]

Sure, I have some troll biscuits in my pocket that I'd like to get rid of.

What is 1/3 as a decimal?

If it has a decimal representation at all, then it is .333...

That is to say that it is a decimal point followed by an infinite
number of 3s.

So what is .333... * 3?

Of course it's .999...
which implies .999 followed by an infinite number of 9s. As you say:

No matter how far back you get, there's a 9 at the end.

But .333... is equal to 1/3.

1/3 * 3 = 1

Thus, .333... * 3 = .999... = 1

QED

I find the notion of repeating decimals kind of silly, and would just
prefer to say that 1/3 has no exact representation. As far as I can
tell from calculus class this doesn't change anything.

Re:I'll be first to say WTF

[david_thornley]

I've seen a claimed polynomial algorithm before where the exponential portion was made very small and hidden away. It may have been polynomial for all reasonable test cases, but given large enough input it was going to be exponential. Test cases prove nothing.

Re:I'll be first to say WTF

[BrotherBeal]

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.

Re:I'll be first to say WTF

[Anonymous Coward]

You didn't learn about convergence in whatever passes for precalculus mathematics in your country.

Re:I'll be first to say WTF

[Anonymous Coward]

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.

I've noticed people use it that way more and more, though. Guarantee is, more or less, replacing "opine," just as literally is replacing "metaphorically."

Re:I'll be first to say WTF

[ailnlv]

you're probably just trolling, but this statement has been proven to be true over and over again. Your mistake is thinking that you have to stop at some finite point. If that is the case then yes, 0.9999 is less than 1, but the sequence of nines is infinite.
Think of it this way. Say there is a finite number of nines. In that case, you'd have that
1=0.9999...+e
where e is a finite quantity. The thing about e is that the more nines you add at the end, the smaller it gets. After some finite but incredibly big number of nines, e should be extremely close to 0, but still greater than 0. But the fact is that if you add an infinite number of nines (where infinite could be defined as a number greater than all natural numbers), e will be exactly 0. Therefore, 1=0.9999...+e=0.9999...+0=0.9999...

Re:I'll be first to say WTF

[Anonymous Coward]

Because, duffus, the rules you were taught about run-on numbers weren't right. Maths follow a clearly enumerated set of axioms; those axioms can be used to derive theorems that have as their consequence 0.99... == 1. That it's unintuitive is more a reflection of you, rather than "magic". It's not magic at all. It is "believed" because that's the consequence of the derivation.

http://en.wikipedia.org/wiki/0.999...

Re:I'll be first to say WTF

[Anonymous Coward]

What end?

Re:I'll be first to say WTF

[retupmoca]

For instance, the whole 0.999... = 1 thing. I think that's a load of crap. You can bring in all sorts of complex calculations, but the fundamental rules (as we're taught) say a run-on number like 0.999... goes on forever. No matter how far back you get, there's a 9 at the end. That 9 isn't going to get a 1 added to it and start a domino effect to magically make it 1.

It's not that 0.999... turns into 1, 0.999... IS 1. 0.999... is simply another way to represent the number 1, just like 2/2 is. Not only that, there is no 9 at the end because there is no end.

Re:I'll be first to say WTF

[Captain Segfault]

The proof is that there is no proof.

This is one of those extraordinary-claims-require-extraordinary-evidence cases. "I tried random inputs" is not good enough. To take it seriously, those random inputs should correspond to hard problems -- for example, use this supposed 3-SAT solver on reductions from integer factoring to factor an RSA number.

Re:I'll be first to say WTF

[bunratty]

There isn't a 9 at the end. That's what the ... means. There is no end. If you sum 9*10^-n for all positive integers n, you get 1.

Re:I'll be first to say WTF

[LanMan04]

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. Unless you count logic as part of math, but I don't.

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.

Re:I'll be first to say WTF

[fishbowl]

The courses where you learn these concepts come *long* before getting CS degree, although I don't expect anyone but a CS or CIS or CSE or a math major to actually take such a course.

3-SAT is typically the first case you consider, as soon as you get past the stage of deterministic finite automata and learning about what is and what is not computable. Then you get into classification of algorithms before you start the heavy analysis.

According to the book I used in the dark ages (Garey/Johnson ISBN 0-7167-1045-5)

3SAT is
3-SATISFIABILITY
INSTANCE: Collection C = {c[1], c[2], ..., c[m]) of clauses on a finite set U of variables such that |c[i]| = 3 for 1 <= i <= m.
QUESTION: Is there a truth assignment for U that satisfies all the clauses in C?

The standard proof that this result is NP-complete is pretty simple, which is why to claim otherwise is so astounding.

I'm disappointed with the comments where we go straight from 3SAT to "omg crypto iz broked!!!11!"

I'd be very impressed if someone took the 3SAT result, mapped it onto 3-Dimensional Matching ("3DM", also known as The Optimal Marriage Problem) or Vertex Cover or some other elementary set that is assumed (proven!) NP-complete.

Re:I'll be first to say WTF

[fishbowl]

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

First year, second semester undergrad discrete math topics are hardly "PhD level"...

Re:I'll be first to say WTF

[Anonymous Coward]

The parent post is very insightful. The algorithm in question relies on trading extra memory for the processing power. As soon as they run out of available physical memory the processing requirement curve will shoot up exponentially.

Let say highest degree of the polynomial that bounds solution time is larger than number of dimensions in our universe. Then start increasing values of n. Even if available memory and processing power is fine grained, tightly packed, and evenly distributed over all physical dimensions you still have to send subset of the problem out and fold results back in. If you subscribe to the notion of limited speed of light then it takes time to reach all processing power and get results back.

In general I would say that N != NP and trying to solve unbounded NP problem leads to the expansion of the universe. The formula for 3-SAT upper bound will turn out to include Cosmological constant :)

Re:I'll be first to say WTF

[Anonymous Coward]

This is mostly the problem. There is no 9 at the end, it is infinite.

Look at it another way. Give me a real number between 1.0 and 0.999... , or inversely, there is no real value that you can add to 0.999... to make it 1.0. A+B=C. If A=0.999... and C=1.0, B cannot have any value except 0.

Or, with fractions. 9/9 = 1, right?

Lets say we have 1/9. It equals: 0.11111...

9 * 1/9 = 9 * 0.1111...

9/9 = 0.9999...

Thus 1 = 0.9999...

But this is a simplistic proof that hides a lot of assumptions. If you want more in-depth analytic proofs, you should take a look at wikipedia:

http://en.wikipedia.org/wiki/0.999...

Re:I'll be first to say WTF

[decep]

I think it may be a little more complicated than this. I have been out of school for a while so I am not up to speed on proofs, theorems, etc.

I think the hole in your logic may be that 0.333... == 1/3. I think 0.333... may only be a very close numerical approximation of 1/3, but 1/3 cannot be expressed absolutely as a number (even assuming infinite 3s).

I have read about the issue of 0.999... = 1 several times, but the explanation is much more complex than this.

Re:Nice way to spread malware?

[Anonymous Coward]

Next /. headline: Malware solves P=NP, achieves sentience

Re:I'll be first to say WTF

[minogully]

1/3 has no exact representation.

1/3 WOULD have an exact representation in a different number system.

If we used, say, base 3 instead of base 10, 1/3 would be 0.1

Re:I'll be first to say WTF

[lederhosen]

Do not be silly, the key could have been exchanged earlier, one time pad is an excellent encryption method that has been used in practice.

Factoring is easy if P==NP

[gr8_phk]

First, the discrete logarithm problem is equivalent to factoring - i.e. a problem of one type can be translated into the other. Second, we can construct a binary circuit to compute products, and iteratively apply 3-SAT to narrow down the inputs until we have a factorization. So if 3-SAT is in P, then so is factorization and discrete logarithm. I'm not aware of the opposite being proven - that if factoring is in P, then P==NP does not necessarily follow.

Re:Factoring is easy if P==NP

[kiwix]

Yes, factoring is easy if P=NP, because factoring is in NP. What I said is, we don't know whether it's NP-hard, and those two notions are quite different. Here are quick explanations from wikipedia:

NP: Intuitively, NP is the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs of the fact that the answer is indeed "yes".

NP-Hard: NP-hard (non-deterministic polynomial-time hard), in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP"

Re:I'll be first to say WTF

[godrik]

NP does not stand for Not Polynomial
it stands for polynomial on a non-deterministic turing mahcine.

If P != NP then there is an infinite number of complexity classes between P and NP-complete.

For the record, A problem is NP-complete if it is in NP and harder than any problem in NP.

A problem is np-hard if it is harder than any problem in NP (it may or may not be in NP)

Re:I'll be first to say WTF

[pthisis]

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

What other option is there? It's either polynomial (P) or not polynomial (NP), isn't it?

Being NP-Hard is a much higher bar than simply being in NP. A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H.

Or as Wiki puts it, "NP-hard (non-deterministic polynomial-time hard), in computational complexity theory, is a class of problems that are, informally, 'at least as hard as the hardest problems in NP'."

Yuk!

[elsurexiste]

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.

Re:I'll be first to say WTF

[Adrian Lopez]

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.

Except that nothing you've stated proves that 0.333... + 0.333... + 0.333... = 0.999..., thus making your argument an example of circular logic.

Re:I'll be first to say WTF

[pjt33]

NP doesn't stand for non-polynomial: it stands for non-deterministic polynomial. Informally what that means is that you can do it in polynomial time if you're a supernaturally good guesser. Formally, it means that a solution certificate exists which can be checked in polynomial time.

Re:I'll be first to say WTF

[godrik]

Actually I think that anyone taht does not have a CS degree will not understand why it is important to begin with.

Re:I'll be first to say WTF

[Sique]

No, it is not. Both sequences, 0, 0.9, 0.99, 0.999... and 1, 1.0, 1.00, 1.00, 1.000 approach to the same number: 1.

And because both are Cauchy sequences, and both converge to the same limit, the axioms of the Real Numbers defines the limits of both sequences as being equal.
What mathematicians did was to axiomatically declare 0.999999... and 1 being the same. There is not much to understand about it. It's The Axiom.

Re:I'll be first to say WTF

[Anonymous Coward]

... and your attitude is the reason why i, as a mathematician will always find work :P

oh, and PLEASE write some encryption algoritm yourself. Go on, its primitive arithmetics and logic after all... what could possibly go wrong?

BTW. you fail at classifying everything as "logic". That stuff USES logic, it ISNT logic. Categorisation fail...

Re:I'll be first to say WTF

[Adrian Lopez]

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.

Re:I'll be first to say WTF

[mark-t]

I'm not disputing that point... I'm disputing the GP's use of the word "guarantee". Unless he has proof to the contrary, he cannot guarantee what he is claiming.

Your Math is Minimal

[luis_a_espinal]

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

[w_dragon]

Logic is math. Or maybe math is logic... Either way, if you prove it by writing on a blackboard rather than doing a study or building a crazy expensive matter collider you're doing math. Also do you really think that Encryption can be truly understood without number theory? I think Fermat would like to have a word with you... Or databases without relational algebra? Take a formal logic course outside of the philosophy department and try to claim that logic isn't math, it could hardly be anything else.

Find the fish

[johnwbyrd]

I am trying to parse the article now. There's very likely a fish in there somewhere.

Note that the Cornell library has hosted at least one other "proof" by a Russian researcher that 3SAT != NP (and that TSP != NP as well).

Re:I'll be first to say WTF

[PeterBrett]

0.9999... = 1 - 0.0000... = 1.

No matter how far back you get, there's a 0 at the end. That 0 isn't going to get a 1 added to it and start a domino effect to magically make 0.9999... less than 1.

Wasn't that easy?

Re:I'll be first to say WTF

[DarthJohn]

Deliver the one time pad in person then suddenly any old means of communication are secure as long as your OTP lasts.

Re:I'll be first to say WTF

[Jumperalex]

And if you don't like that

1) 3 * 1/3 = 1
2) 1/3 = 0.3.....
3) 3 * 0.3... = 1
4) 3 * 0.3... = .9...

There for 0.9... = 1

Re:I'll be first to say WTF

[logical1010]

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

Re:I'll be first to say WTF

[Asmodae]

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

Re:I'll be first to say WTF

[bersl2]

This reduces to your not being knowledgeable about limits and the infinitesimal. I suggest that you learn enough calculus to understand infinite geometric series. You can do the proof that way.

Re:I'll be first to say WTF

[Mitchell314]

This isn't opinion,this is mathematical fact that 0.999...=1.
Let x = 0.99999...

So mulptiple both sides by 10:
- 10*x = 9.99999...
Subtract x from both sides
- 10*x - x = 9.99999... - x
Substitute 0.9999.... for x on the right side
- 10*x - x = 9.99999... - 0.99999...
Simplify:
- 9*x = 9
Therefore:
- x = 1
- 0.9999... = 1

Re:I'll be first to say WTF

[Surt]

Do you have evidence that RSA security rests on P != NP? Because I'm pretty sure none of R, S, nor A have figured that out.

Re:I'll be first to say WTF

[kevinNCSU]

Really, y'all proved P==NP in your first year of undergrad and didn't bother sharing it?

Re:I'll be first to say WTF

[skids]

Except that nothing you've stated proves that 0.333... + 0.333... + 0.333... = 0.999...

Well, if you follow the the "logic" of original complaint: No matter how far back you get, there's a 3 at the same place in all three numbers, and that adds to 9. That 9 isn't going to get a 1 added to it and start a domino effect to magically make it change. :-)

Re:I'll be first to say WTF

[Surt]

Integer factorization is not (yet) np-complete, so technically no one can do what you are asking, even if they have a legitimate proof of p=np.

Re:I'll be first to say WTF

[rbayer]

Discrete log is also in NP--I can verify your proposed solution by simply exponentiating it, which is a very fast operation when working in modular arithmetic. In fact, any reasonably normal asymmetrical encryption algorithm pretty much has to be in NP since you can verify a proposed private key for any public key by simply encrypting and decrypting something, both of which should be polynomial time or else the system is probably too slow to be useful anyways.

Re:I'll be first to say WTF

[amRadioHed]

Sure, it's been used. But there are very limited situations where this is practical. Certainly almost none of the encryption on the internet could be done this way. The difficulty of distributing pads can't be hand-waved away.

Re:I'll be first to say WTF

[B1ackDragon]

(Devil's advocate post, ymmv)

While I agree that the result is almost certainly incorrect, IMO his arguments appear to be analytical enough to be considered a proof (perhaps a "sketch," and again, he's likely made a mistake). Even though the arguments are quite rambling, he insists on using too much of his own terminology, and he cites almost no previous literature (though he attempts to justify this near the end.)

Also, he does offer a runtime analysis: O(mn^4) in Section 6. As for the space/time tradeoff mentioned by others, I'm no complexity theorist but as I understand it no poly-time algorithm can use exponential space (how can you access exponential memory locations in polynomial time?)

Finally, the inclusion of real-machine performance isn't that surprising given that he has software: I myself have been asked for this by reviewers even after giving a big-O analysis of the algorithms (in cases where I had produced real software).

Re:I'll be first to say WTF

[Surt]

If you let that kind of post get to you, slashdot is of no use to you.

Re:I'll be first to say WTF

[gfody]

I see people having trouble with this concept time and again and the truth is that it just seems so silly once you understand the different number types. Basically you're confusing the real 0.333... with the rational 0.333. Read more here.

Re:I'll be first to say WTF

[Darinbob]

Cryptography has a ton of math in it now. Ie, probability and statistics to decide how effective an algorithm is, such as why is 128 bit encryption good enough but 64 bit isn't. Or understanding what the heck Elliptic Curve is. Why is SHA-256 better than SHA-1?

Sure there's tons and tons of logic involved. But then mathematics is really a sub branch of logic in many way.

Re:I'll be first to say WTF

[Adrian Lopez]

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

In specific cases the limit of an equation as x approaches y does indeed equal the equation at x = y, but it doesn't work as a general rule therefore you can't say it's the same thing.

Re:I'll be first to say WTF

[ChromaticDragon]

No.
That's not the circular part.
That part is relatively trivial. Do forgive trying to express this in ASCII...
Sum[from 1 to infinity]{3/(10^n)} is 0.3333...
This is just the basic definition of what that means.
3 * 0.3333...
= 3 * Sum[from 1 to infinity]{3/(10^n)}
= Sum[from 1 to infinity]{3*3/(10^n)}
= Sum[from 1 to infinity]{9/(10^n)}
= 0.9999...

Again this is pretty basic arithmetic, distributive property of multiplication if you want to be pedantic.

No, the circular part of the logic is starting with 1/3 = 0.333... to show you 1 = 0.999... Why in the world do you believe 1/3 = 0.333...? But this is why folk earlier suggested that if you had no issue with 1/3 = 0.333..., then you shouldn't have any issue with 1 = 0.999...

At any particular n, the sum is less than the fraction it represents. This the same issue for 1/3 as it is for 3/3 or 1.

Re:Russia

[camcorder]

And you just realized that? If so I think you still have time to drink some vodka.

Re:I'll be first to say WTF

[Aristos Mazer]

No. It is possible that you might get the degree after you start reading slashdot.org. But, really, going through life without a CS degree? How will you organize people at a party all trying to dip chips into a salsa bowl unless you know the exponential backoff algorithm?

Re:I'll be first to say WTF

[Anonymous Coward]

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.

Since I'm interested in this particular field, allow me to point to a column that appeared in the ACM SIGACT News a couple of years ago, containing the results of an informal poll among mathematicians about their opinion on P=?NP and their estimates when this problem would be solved.

The majority of them (but not all) believe that indeed P!=NP; several also thought that P=NP, or that the question of whether P=NP was independent (of ZFC). A significant number also did not commit to an opinion either way.

There's a PDF available here, too.

-John

Re:I'll be first to say WTF

[TerranFury]

For instance, the whole 0.999... = 1 thing. I think that's a load of crap. You can bring in all sorts of complex calculations, but the fundamental rules (as we're taught) say a run-on number like 0.999... goes on forever.

What does the sequence of symbols 0.9999... actually mean? That's your problem. You need to get clear on what a real number is before you can tackle that. I agree that the "proofs" using simple algebra are unconvincing, because, again, they just blindly apply operations to these sequences of symbols without considering their meaning.

One way to define the real numbers is as Cauchy sequences of rationals under an equivalence relation. Rationals are in turn defined in terms of integers, which are defined in terms of naturals. Understand the definitions and everything will start to make sense. Math isn't universal truth; it's just stuff people made up: Figure out what, exactly, the standard definitions are.

Canonical Slashdot Explanation

[billstewart]

1 - First you steal all the math problems
2 - .... , potentially with exponentially many dots
3 - PROFIT!!

This paper said you might not need as many dots in step 2, so you get to PROFIT sooner!

Re:I'll be first to say WTF

[bzipitidoo]

Guessing which car matches the criteria, or which half of the lot to check first, and being correct, is the talent of an oracle. Oracles don't really exist of course, they're just imaginary things used for reasoning about these problems. Nondeterminism is not having to guess, not having to choose one car at a time (determine which car to look at next) to check for a match. All possible solutions could be checked in parallel.

How? There is no known practical way to do that. Imagine if the salesperson could call on an army of fellow salespeople who can each check a different car. If there were enough, each one would have to check only one car, and the correct car would be found very quickly. Unfortunately, it is much easier to make the lots impossibly big than to assemble enough salespeople to handle any size lot. Another way to achieve such parallelism is if you can use quantum superposition, as in Shor's Algorithm for factoring. Since we haven't managed to handle more than a very few quantum bits for more than a few seconds, we haven't been able to try out Shor's algorithm on any sizable factoring problem. Even if we could, we don't know if 3-SAT (or any other NP complete problem) can be formulated so that quantum superposition could be applied. In other words, factoring may be an easier problem than 3-SAT but still harder than a problem in P.

Re:I'll be first to say WTF

[Anonymous Coward]

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, you do get 1 = 0.999...! Why would you not? Each and every 3 turns into a 9. This just simply shows that 1 = 1 and 1 = 0.999... express the exact same thing.

Your limit analogy is both flawed and completely irrelevant.

Romanov's "algorithm"

[johnwbyrd]

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:Romanov's "algorithm"

[Anonymous Coward]

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

Furthermore, we know that resolution is at least as powerful as any other truth-table based method, and it has been proven that certain NP problems require resolution certificates that cannot be generated in P.

If he's using truth tables, it's trivial to prove that his proof is flawed.

Re:I'll be first to say WTF

[Darinbob]

If your system has a fixed amount of memory, then I suggest that they really added O(1) to your projects :-)

Ie, I do linear searches all the time in code, and put that in a loop so that it resembles "O(n^2)". However when I know my linear searches are highly bounded (max array size of 8 :-) then it's not an issue.

I've seen programmers go too far the other way. Using C++ maps for something that should be a trivial array lookup, and then sticking that in a critical loop, then wondering why everything is so slow and memory is getting fragmented.

Re:I'll be first to say WTF

[psmears]

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.

Discrete log is in NP. Knapsack is in NP. In general, if a solution to a problem can be checked in polynomial time (regardless of how difficult it is to actually find that solution in the first place, which might be much harder), then the problem is in NP. Since for practical purposes encryption/decryption needs to be fairly quick, it's likely that a lot of encryption algorithms will fall into this space...

Re:I'll be first to say WTF

[Adrian Lopez]

Well, if you follow the the "logic" of original complaint: No matter how far back you get, there's a 3 at the same place in all three numbers, and that adds to 9. That 9 isn't going to get a 1 added to it and start a domino effect to magically make it change. :-)

That's an interesting and appealing point, but intuitively it seems to me like looking at the problem from the wrong direction (left to right rather than right to left). Don't know what to make of it, though.

Re:I'll be first to say WTF

[migla]

If 1/3 is 0,33333... then 0,99999... is 1.

Re:I'll be first to say WTF

[Asmodae]

We aren't talking about the general case, we're talking about the specific case of .999... == 1. In fact I clearly stated that it's a way to solve for the limit when the function is defined at that point which explicitly defines the specific cases where applicable.

Also, you've yet to explain why 3*.333... == 1 and not 3*.333...== .999..., but 2*.333... == .666... just because I write 1/3 or .333... doesn't mean they're different numbers. Same with 3/3 and .999... and 1. Just 3 different ways to write the same thing.

Re:I'll be first to say WTF

[PaladinAlpha]

Well, no. In ALL cases where f(x) exists, the limit of n as n approaches x is ALWAYS f(x). It is the same thing.

Kindly explain to me how 0.333... * 3 = 1, if 0.999... != 1.

Re:I'll be first to say WTF

[psmears]

RSA does not depend on P vs NP.

Unfortunately that's not true...

It is currently an open question what the complexity of factoring is.

That's true, but it is known that it's in NP—what's not known is exactly where in NP it fits...

Re:Nice way to spread malware?

[Anonymous Coward]

If this solution is true his algorithm is going to be published in the most famous journals and being taught at university starting next semester. Safety by obscurity has been proven wrong many times and hiding the source code to a soon-to-be published algorithm is not going to do anything.

Re:I'll be first to say WTF

[jpate]

I think the hole in your logic may be that 0.333... == 1/3. I think 0.333... may only be a very close numerical approximation of 1/3, but 1/3 cannot be expressed absolutely as a number (even assuming infinite 3s).

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.

Re:I'll be first to say WTF

[Remus Shepherd]

Not all geeks are computer geeks. I'm a physics geek myself, so I can run an experiment to see if something is true or not, which means that P/NP problems are alien to me. Fascinating approach, though.

Re:I'll be first to say WTF

[Darinbob]

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.

More consequences besides cryptography

[Quackers_McDuck]

People always talk about the impact P==NP would have on cryptography, but a much more world-changing impact would be on mathematics:

...it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time. Example problems may well include all of the CMI prize problems.

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

Re:I'll be first to say WTF

[Darinbob]

Oh yea, factor me again!

And none of this "assume a non deterministic Turing machine" solution like you're in a hurry, I want the full P-time and P-space satisfaction!

Re:I'll be first to say WTF

[m50d]

I think it may be a little more complicated than this.

No. It's not complicated.

I think the hole in your logic may be that 0.333... == 1/3. I think 0.333... may only be a very close numerical approximation of 1/3, but 1/3 cannot be expressed absolutely as a number (even assuming infinite 3s).

No. 0.333... == 1/3 by definition; that's what the notation means. You're thinking about this wrong; a decimal isn't a "numerical approximation", it's notation for, well, if you want to get technical about it then the notion of a Dedekind cut may help.

The standard argument for why P!=NP

[billstewart]

Lots of really smart mathematicians have been trying to find proofs that P==NP for a long time, and they've got lots of good tools to work with. None of them have succeeded. They've also been trying to prove that P!=NP, but that's probably much harder to prove, or at least to validate, since a constructive proof that P=NP has lots of testable examples.

Occasionally people make assertions that they've got a proof that either P==NP, or P!=NP; if they're smart they get them peer-reviewed and find the mistake, but maybe they get to improve our understanding of the general problem or some more specific hard problem, so at least they get a paper out of it. If they're not smart, they just publish it on the InterWebs, and either become net.kooks or have someone gently explain to them how the academic research process works, but the fact that they don't know suggests that they haven't read all the standard research. If they're greedy, they try to patent it, and if it gets past the Patent Examiners they can try selling it to a Patent Troll.

Re:The standard argument for why P!=NP

[mcelrath]

You appear to have used a sociological argument as proof of a mathematical statement.

You fail.

Insufficient creativity is proof of nothing. I know lots of widely-held beliefs by experts that are provably (and some already proven) false.

Once, the entirety of living experts believed the earth was flat, the sun went around the earth, animals did not evolve, etc, etc. They were wrong too.

Re:The standard argument for why P!=NP

[mcelrath]

I have replied to the wrong post. Sorry.

Re:The standard argument for why P!=NP

[billstewart]

> You appear to have used a sociological argument as proof of a mathematical statement.

Absolutely correct!

> You fail.

No. It's not meant to be a conclusive proof, it's just the way to bet. A proof that P=NP would be Really Cool, and do all kinds of really useful things for the Real World as well as for mathematicians, even though for a cryptographer or computer security designer it would be a major pain in the ass\\\\\\\\\ New Business Opportunity.

We've already got to deal with Quantum Computers as a potential future threat model, so we're not forgetting how to do hashes and Key Distribution Centers, and making sure to design protocols that let you use longer key sizes if you need them, and if P=NP we'll have to live with that as well, though it probably tips the balance to make it possible for a government-sized attacker to beat a PC-using communicator, as opposed to today when it's the other way around.

I've already been through this sort of thing before. I was an operations researcher in college, and a couple of years after I graduated, Karmarkar came out with his linear programming algorithm, which was in P rather than exponential like Dantzig's Simplex algorithm. On the other hand, simplex was usually pretty fast, and almost never in the slow cases for real problems, and Karmarkar's was something like O(n^6), which was annoyingly slow and large for real problems, but computers have been gotten a lot faster in the last three decades. On another hand, the Internet and computerized typesetting have made the Net.Kook problem much harder than the days that kooks had to use carbon paper and bad typewriters.

Re:The standard argument for why P!=NP

[mcelrath]

Oh I did reply to the right post. I went looking for who posted your bold part, thinking afterwards that it was a quote from the parent. I ride the failboat.

Anyway, I'm just sick and tired of "folk wisdom" being used in place of proper scientific reasoning. It closes doors, and causes otherwise smart people to ignore promising avenues of research. The fact of the matter is, when the majority of the scientific community has examined a problem, and keeps coming up with the same contradictory solution (or a null solution, in this case), it is likely there is an ideological cancer or unexplored avenue that lies just around the corner, for the person willing to ignore "folk wisdom".

As for betting, you're betting with the crowd. Any idiot monkey can do that. The odds are shit, and black swans define the future.

I strongly believe it is the scientific community's responsibility to refute the kooks. In times of serious herd-ism, the revolutionary will, at first, be identified as a kook. This particular guy has communicated his idea in a clear, and most importantly, falsifiable (codified) manner. (Unlike many incoherent kooks) Many things can be easily rejected on grounds of coherency. Trying to understand incoherent kooks is the path to madness... Don't ignore the clear, lucid kooks for sociological reasons. Societies are herds, and are collectively dumb, even when composed of scientists. Prove the kooks wrong instead.

Re:I'll be first to say WTF

[Asmodae]

Why is this sudden addition necessary to 'make it roll-over'? I wrote this slightly above, but it is a good clear example to repost:

1/3 == .333... given
3*.333...== .999...
2*.333... == .666...
3*1/3 == .999...
3*1/3 == 3/3 == 1 == .999...

just because I write 1/3 or .333... doesn't mean they're different numbers. Same with 3/3 and .999... and 1. Just 3 different ways to write the same thing.

Re:I'll be first to say WTF

[Adrian Lopez]

Well, no. In ALL cases where f(x) exists, the limit of n as n approaches x is ALWAYS f(x). It is the same thing.

Key words being "where f(x) exists".

Kindly explain to me how 0.333... * 3 = 1, if 0.999... != 1

I can't unless I explain it in terms of fractions. Getting 0.999... from 0.333... strikes me as an artifact of notation rather than one of quantity, but I admit this is something I can't prove.

My favorite paper on "proofs"

[russryan]

Social Processes and Proofs of Theorems and Programs by DeMillo, Lipton, and Perlis. Let the social process begin.

Re:I'll be first to say WTF

[marcosdumay]

Ok, let's go off-topic here. What is the difference (really, subtract) between 0,9999... and 1?

Re:I'll be first to say WTF

[Adrian Lopez]

Also, you've yet to explain why 3*.333... == 1 and not 3*.333...== .999..., but 2*.333... == .666...

Interesting. I'm stumped.

Re:I'll be first to say WTF

[marcosdumay]

That is wrong. In all cases where F(x) is CONTINUOUS near x0 the limit of f(x) when x -> x0 is equal to f(x0).

Re:I'll be first to say WTF

[Anonymous Coward]

Not true. You can legitimately have a function that is defined as:

f(x) = 42 if x is 3; x if otherwise

The limit of f(x) as x approaches 3 is 3, but f(3) is 42. Your statement holds for all cases where f is continuous. In fact, your statement is the definition of a continuous function.

Re:I'll be first to say WTF

[drewhk]

Yes, exactly! In fact 0.333... is just a notation for the number that is the limit of the series: 0.3, 0.33, 0.333, ..., and that limit is exactly 1/3.

Re:I'll be first to say WTF

[PaladinAlpha]

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

[Anonymous Coward]

.5 * 10 = 5
5 - .5 = 4.5
4.5/4.5 = 1
.5 = 1 Q.E.D.
Isn't using arbitrary numbers to prove something awesome?

Re:I'll be first to say WTF

[Fuzzy Eric]

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

Re:I'll be first to say WTF

[Broolucks]

The fact that 1 = 0.999... is itself an artifact of notation. 1 and 0.999... are two equivalent notations for the same real number. There is nothing particularly strange about that.

Re:I'll be first to say WTF

[BitterOak]

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.

True. But real numbers happened to be defined as limits. More precisely, they are equivalence classes of Cauchy sequences of rational numbers, which two such being considered equivalent if they converge to the same limit, i.e. |a_n - b_m| < epsilon, where m, n > some k which depends on epsilon. By this definition, 0.9999... is exactly equal to 1.

Re:I'll be first to say WTF

[Anonymous Coward]

http://xkcd.com/287/

Not exactly the same problem, but at least of the same class.

Re:I'll be first to say WTF

[Anonymous Coward]

Thank you :)

Re:I'll be first to say WTF

[Adrian Lopez]

Right, and 1 exists. QED.

Care to state the argument -- that 3 * 0.333... = 0.999... -- in terms of limits? I brought up limits only because I think it's useful to look at 0.999... as a number approaching 1 as the number of digits to the right approaches infinity. I still don't see how x * 0.333... equals 0.999... (rather than 1) as x approaches 3.

Re:I'll be first to say WTF

[marcosdumay]

As was already said, it is polynomial time, not linear. Now just proving that P=NP may not make an algorithm appear out of thin air, but it is quite likely that any proof of that will be done by creating such algorithm. And, by the way, that is the case here, the proposed proof is in the form of an algorithm.

Make your own

[MrEricSir]

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

Re:I'll be first to say WTF

[Lobachevsky]

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

[johanatan]

because translating a solution of a NP-complete problem to a solution of any other NP problem is itself O(some polynomial of n)

Are you sure about that? I thought the idea was to translate instances of the more difficult problems into instances of the easier problems (and then to use the solution you already have for the easier problems). Also, a solution is by definition generic--otherwise it wouldn't be much of a solution. And, it doesn't really matter how much time it takes to 'translate a solution' because if it truly is a solution, you should only have to do it once.

Re:I'll be first to say WTF

[Cinder6]

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.

Re:I'll be first to say WTF

[Ihmhi]

Considering that my post was modded overrated, I'd like to preface the following by saying that I am in no way trolling. I genuinely lack the understanding of the concept.

Well this would fall under theoretical math and not practical math, would it not?

I hear the:

1/3 = 0.333...

1/3 x 3 = 1

>

0.333 x 3 = 0.999...

Therefore 0.999 = 1

...argument and it honestly doesn't quite yet make sense to me.

One of the later things I learned was that mathematics is taught in stages. i.e. when you're very young you may be taught that 0 is the start, but a few years later they break out negative numbers on you, and so on.

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. (I am not making a statement of fact here per se; I am merely stating the concept as it was taught to me).

Perhaps you can help me by explaining further; I'm going to respond to your post point by point as I understand it. The simpler you can explain it, the better - once I got into the higher maths like calculus I had a very difficult time wrapping my mind around a lot of the theoretical stuff.

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?

Nothing, but what is the significance of there being nothing between 0.999... and 1? If there is nothing between 0.999... and 1, then you would not the logical conclusion be that there is nothing between 0.888... and 0.999..., therefore 0.888... = 0.999..., and since 0.999...... = 1 then 0.888 = 1 as well?

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.

Ah, when you say this I can understand it a little better in a way - the infinite nature of it therefore means that nothing can be added to it to make it 1, therefore it is 1... but I don't quite get why the fact that it runs on forever and nothing can be added to it (because of its infinite nature) makes it equal to 1.

But even so, why would one make the assertion that 0.999... = 1 because nothing can be added to it? Could you not just as easily make the assertion that because nothing can be added to it, 0.999... is not 1?

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?

Well, obviously 1/3 x 3 = 1, and .333... x 3 = .999..., but as I've said I've always been taught that .333... is not exactly equal to 1/3; it is just the best approximation we have.

Honestly, it seems more metaphysical or theoretical to me - a sort of Zen Math version of "All roads lead to Rome" ; "all run-on decimals are in 1". I'm usually more concerned with practical mathematics over theoretical mathematics, but I am genuinely stumped by this.

Honestly, I wish someone could just draw me a picture, but I probably wouldn't be able to view it since my graphics card doesn't go to the Infinity x 768 resolution. d:

So, in short, to number and summarize my questions (and I apologize to both any who read and/or reply to this as well as all of my past and future teachers who I've constantly nagged with my inquisitive nature):

.

1) If you make the assertion that 0.999... = 1, would making the assertion that 0.888... (or 0.777..., or 0.34667777..., etc.) are also 1?

2) Is the assertion that 0.999... = 1 because of the infinite nature of a run-on number?

3) If so, why?

4) If not, then what is the property that would cause one to make the asse

Re:I'll be first to say WTF

[dvdkhlng]

There are so many errors in your comment that I almost don't know where to start:

• Integer factorization is not NP-hard (which would imply it is outside NP), it is in NP
• Being in NP, but not NP-complete means, that it is probaly "easier" then 3-SAT (look at this diagram describing relations between complexity classes)
• The discrete logarithm problem can be implemented via factorization and vice versa. If you can easily solve one, you can easily solve the other

Re:I'll be first to say WTF

[Cinder6]

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.

Re:I'll be first to say WTF

[gfody]

er said that backwards, it's rational 0.333... and real 0.333
also, the number types tend to have infinities between them making the more complex ones infinitely more useful. for instance there are an infinite number of real numbers in the form of 0.33..3 that are not equal to 0.333...

Re:I'll be first to say WTF

[Chapter80]

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]

P = ?

[Mandrel]

what does P stand for?

Portman.

No no. We know that P is Porter.

Re:I'll be first to say WTF

[Jah-Wren Ryel]

Who are you the fucking geek police? Fuck you! You don't get to dictate to us which of us are and aren't geeks. Fucking asperger retard....

The geek police, they live inside of your head
The geek police, they come to you in your bed
The geek police, they're coming to arrest you, oh no

You know that posts are cheap
And those AC's ain't nice
And when you fall asleep
I don't think you'll survive the night, the night

'Cause they're waiting for you
They're looking for you
Every single night they're driving you insane
Those men inside your brain

factoring != DLP

[0ptix]

I'm pretty sure factoring and discrete log are not known to be equivalent. This would be a huge result in theory of crypto if it could be shown.

Re:factoring != DLP

[gr8_phk]

Here's what google has to say about it. I thought I had worked through it myself a while back, which would mean it's not hard to prove :-) However, these papers suggest it's not that easy.

Re:I'll be first to say WTF

[khellendros1984]

Think about it from the other direction. You'd agree that 1.0-0.999...=0.000...1, right? So follow those zeroes....where is the 1 that "magically" gets added to 0.999...?

Re:I'll be first to say WTF

[Anonymous Coward]

ya, but 9.999... (from step 1) minus .9999... (from step 2) doesn't = 9 (not all infinities are the same)
when you multiply step 1 by 10, you lose 1 significant digit off the decimal. so the infinite expansion from step 1 is infinitesimally larger than the decimal expansion in step 2.

So your step 3 is wrong. it should more appropriately read (9.0000.....9) / 9 = (1.0000.....1)

Re:I'll be first to say WTF

[rwa2]

So in that representation you're pretty much saying that:

lim x->infinity (0.1)^x = 0

What's interesting is that instead of 0.1 you can substitute 0.9 or 0.999 or anything between (-1 .. 1) exclusive and still end up with zero. Dunno how that translates into infinitely repeating decimal digits, tho :-P

/ Stupid slashcode filtering out HTML and unicode infinity symbols :-P

Re:I'll be first to say WTF

[catmistake]

(Love most of your post... been posting similarly for days.... but... ) What engineering? Software what what? It makes more sense to call a barber a hair style engineer than it does to use weird meaningless marketing terms like "software engineering." I have the greatest respect for programmers, computer scientists, and bone fide engineers... but I just feel sorry for anyone with either such low or far too elevated self-esteem to refer to themselves as a software engineer. It's no better than "sales engineer." Coding is respectable in it's own right without having to synthetically prop it up with a false title. Call me a flamebait engineer.

Re:I'll be first to say WTF

[Anonymous Coward]

That's an oft-repeated explanation that 1 = 0.999...

However, I have seen sources (I'm not quite sure how reliable) that say that your explanation lacks sufficient rigor to be considered a "proof".

Can anyone comment about whether the parent's explanation can legitimately be considered to be a "proof"?

It certainly "feels" like a proof to me, but that may be due to my ignorance.

Re:I'll be first to say WTF

[kbolino]

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.

ALL asymmetric crypto rely on P != NP

[0ptix]

Here's your evidence:

Given a public key for an asymetric cryptosystem (say a modulas n for RSA) it is easy to verify (i.e. in NP) that a candidate secret key (say primes p and q in the RSA case) match the public key. Paraphrasing heavily now: If P == NP then anything that is easy to verify if polytime is also easy to solve in polytime. In our case that means if i give you a public key you can now FIND a matching secret key in polytime. I.e. if i give you n which is an RSA public key you can factor it into primes p and q. But if you can find the secret key for any public key algorithm (including RSA) then no such algorithm can be a "secure" cryptosystem.

Heading off some misunderstanding: We do not know how to base security ONLY on P != NP. In fact that is considered one of the largest open problems in modern theory of crypto. While I just argued that P!=NP is a _necessary_ condition for all asymmetric (and most symmetric) crypto to be secure it is not known to be _sufficient_.

We're getting closer with some of the recent advances in Lattice based crypto but were are definitely not their yet. For the theory people out there: A fundamental problem here is that NP tells us something about worst case hardness but for crypto we need average case hardness (i.e. for a random secret key and random coins for the ciphertext). Bridging this gap is highly non-trivial. Recent work in lattices has shown such connections and how to use it for certain problems. However the choice of parameters we use for the resulting cryptosystems are not known to result in NP-hard underlying problems.

Re:ALL asymmetric crypto rely on P != NP

[Surt]

What you've shown is well known, that if P=NP, there exists an algorithm that will solve crypto in polytime.

But RSA encryption relies on an efficient algorithm being unknown, not on its non-existence.

Re:I'll be first to say WTF

[Anonymous Coward]

Orgasm doesn't necessarily imply sex.

Re:I'll be first to say WTF

[catmistake]

The difference between say, computer science and sociology, is that computer scientists require absolute proofs.

Fallicious! Not all sociologists and computer scientists are drunks!

Re:I'll be first to say WTF

[gfody]

before you start checking every car on the lot you might want to see if the 24 conditions can even be met. that's the boolean satisfiability problem and it's proven np-complete. the problem isn't finding the car, it's determining if you should bother to look.
3SAT is a special case of a special case of that problem so the car analogy would be way contrived and less interesting. 3SAT was thought to be proven np-complete though so this result is interesting at least in that it disproves that.

Re:I'll be first to say WTF

[Tyler Durden]

ya, but 9.999... (from step 1) minus .9999... (from step 2) doesn't = 9 (not all infinities are the same)

The number of digits in 9.999... and .9999... are both countably infinite. These infinities are the same. A countably infinite set + 1 (or any finite amount for that matter) is still countably infinite.

when you multiply step 1 by 10, you lose 1 significant digit off the decimal. so the infinite expansion from step 1 is infinitesimally larger than the decimal expansion in step 2.

"Infintesimal" is another way of saying "non-existent". An infinitely small quantity is zero. Newton and Leibniz thought otherwise when they created calculus, but we now know that they were wrong.

So your step 3 is wrong. it should more appropriately read (9.0000.....9) / 9 = (1.0000.....1)

The "numbers" 9.0000...9 and 1.00000...1 are fictitious. Putting a digit at the "end" of what you define as a string of digits without end is illogical and thus, meaningless.

Re:I'll be first to say WTF

[Barrie_rdv]

NP is the set of all problems for which an alleged solution can be checked in O(some polynomial of n).

That is a common mistake. NP means that a non deterministic Turing Machine (a Turing Machine that can "guess" the right path to take if faced with a choice) can solve the problem in polynomial time. It has nothing to do with the time to check the solution.

Re:I'll be first to say WTF

[Anonymous Coward]

You can solve any P problem in polynomial time, so reductions have to be less powerful (most likely you used NL).

Make it try AES

[Myria]

What would happen if you tried to express cracking an AES key in 3-SAT form then asked this program to solve it? Will it have to introduce exponentially more variables?

I figure that if anyone claims to have a 3-SAT algorithm, we should ask it to try something infeasible like crack an AES key.

Re:Make it try AES

[Anonymous Coward]

What would happen if you tried to express cracking an AES key in 3-SAT form then asked this program to solve it? Will it have to introduce exponentially more variables?

I figure that if anyone claims to have a 3-SAT algorithm, we should ask it to try something infeasible like crack an AES key.

Two problems:

1. AES is not proven to be an NP problem (since integer factorization isn't proven to be an NP problem). It's hard to map a problem to another when you don't understand it well enough.

2. P doesn't mean fast. His paper claims that his 3-SAT algorithm is O(n^4e6). That's polynomial, but it would still take a *damn long time* to crack AES :)

Re:Make it try AES

[Anonymous Coward]

While cracking AES wouldn't unconditionally prove that the algorithm solves every instance of 3-SAT, it's metric buttload more impressive demonstration of its efficiency than just about anything else.

The very design of symmetric ciphers is that they attempt to approximate the problems most difficult to invert.

Re:Make it try AES

[Anonymous Coward]

AES, being a symmetric key cipher, has almost noting to do with integer factorization.

AES has been written as a SAT problem, so it can be reduced to a 3-SAT problem. Which this dude's code could solve.

Re:Make it try AES

[ShadowRangerRIT]

Correct me if I'm wrong, but AES's strength has nothing (or little) to do with P==NP. AES is private key cryptography, and doesn't rely on exponential time-to-solve mathematical problems. You're probably thinking of RSA (and other related public key crypto systems) where the central problem (factoring the product of two large primes) is NP (though unlike 3-SAT, it's probably not NP-complete). RSA is used for key exchange to enable the primary crypto channel (in AES or another private key crypto system), so for stuff like online shopping a break in RSA is effectively equivalent to a break in AES, but it's not actually breaking AES, you're just grabbing the key before it even gets used.

Re:Make it try AES

[kylemonger]

It doesn't matter what the encryption algorithm is, it only matters if a valid decryption can be verified in polynomial time. If it can, then the problem is in FNP and you should be able to formulate a decision problem in NP for it. Once you have that decision problem, whatever it is, it can be converted into a 3-SAT instance. That is the terrifying power of NP-completeness.

Since the point of encryption is having a recognizable message after decryption, it's safe to assume that whatever the encryption algorithm, a valid decryption would be recognizable in polynomial time. Thus all useful encryption algorithms would be rendered useless by a tractable universal solution to 3-SAT problems. Fortunately, it is unlikely that the Romanov has such a solution.

Re:I'll be first to say WTF

[Nurgled]

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

[Anonymous Coward]

So the analogy breaks down a bit.

We can assume car dealers have a finite amount of cars. So they can just check each car and see if it fulfills all the requirements. Such a test is clearly polynomial.

3-sat would be a more theoretical question like: can such a car exist? or what is the full set of all the combinations possible to satisfy the customer?

A better analogy would be to go to a car factory and ask for those features for a designer car.

paste this

[geekoid]

javascript:document.body.appendChild(document.createElement('div'));

into a link and bookmark it. I have it on my bookmark bar and when ever I need to paste into slashdot I click on the textbox then the button in my bookmark bar labels Fix /.

Re:I'll be first to say WTF

[lee1026]

The formal definition is for Turing machines, which was infinite storage.

Re:I'll be first to say WTF

[Anonymous Coward]

Well then, apparently you only count counting as math.

If so, I don't see how anything could be significantly more math-centered than paying bills. I mean, you stuff numbers into a calculator and blam - there's the answer. Of course when building a bridge, you need to input a few more numbers, but then again it's a bigger project overall so the portion of "maths" isn't that much different.

Back to real world: Yes, pretty much every maths student counts what you're referring to as logic as math. In fact it's pretty sizeable portion of what they are studying.

Re:I'll be first to say WTF

[geekoid]

I was going to show you a proof, but you have been bitch slapped quite soundly.

Well done /.

Re:I'll be first to say WTF

[Burnhard]

We called it Discrete Mathematics at my University.

Best car analogy:

[geekoid]

Get into your car. Drive to the college. Take some courses.

Re:I'll be first to say WTF

[didroe84]

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

[StikyPad]

if you claim that P==NP, as this paper does, then I require you to show that it is so for all possible inputs.

Even if he did that, does it necessarily follow that P=NP, or could it mean that the proof of NP-completeness for 3-SAT is flawed?

Re:I'll be first to say WTF

[Anonymous Coward]

I saw it come true in my dreams. Ergo: It's true for me QED NP = P.

Re:I'll be first to say WTF

[makomk]

As several other people have pointed out, NP doesn't mean not polynomial, it means polynomial on an non-deterministic Turing machine (i.e. you can test whether a solution is correct in polynomial time). What's more, P is a subset of NP - any problems that's in P is by definition also in NP.

Re:I'll be first to say WTF

[StikyPad]

I think you should post the it one more time just to see how many times the same post by the same person can get modded up in the same thread of the same discussion. :D

Re:I'll be first to say WTF

[caerwyn]

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.

Re:I'll be first to say WTF

[Iron Condor]

There is nothing special about the number ten or a ten-based system of expressing numbers

Please restate your objection, expressing all numbers in base-3

Re:I'll be first to say WTF

[SanityInAnarchy]

Well, except that universities are offering "Software Engineer" degrees, which are significantly different than "Computer Science". Both involve coding, sure, but the focus is entirely different.

Re:I'll be first to say WTF

[Anonymous Coward]

The real problem is that the proof is in NP.

Re:I'll be first to say WTF

[Noughmad]

So, you're saying that NP=P means "Natalie Portman is Portman", which would make it prior art for the "Long cat is log" meme?

Whatever happened to the old NP=NP, as in Natalie Portman is Naked and Petrified?

Re:I'll be first to say WTF

[gd2shoe]

You probably don't have a problem with the idea that 1/3 = .333...

I do, actually, on a deep philosophical level. (I'm usually pragmatic enough to let it slide.)

... so if there is nothing that you can add to the first term to turn it into the second, they must be the same.

That's a big if. Actually, there is something you can add to turn 0.999... into 1. I'll give you a hint, since they're infinitely close together, the term must be infinitely small...

Technically, they simply cannot be the same because 1 belongs to the group of integars, and 0.999... doesn't. "Seems pretty common sense, huh?"

Re:I'll be first to say WTF

[NoSig]

His mistake, if he indeed did what you said, is completely consistent with the way the NP versus P question is usually popularized. Your refutation clearly points out how the NP versus P question isn't actually relevant to actual computation by actual computers - it is a theoretical concern that is useful to know about when e.g. trying to come up with algorithms. However the question is often presented as though it is a practical concern and if that were true his methodology would be sound.

Trinary

[gd2shoe]

I think the hole in your logic may be that 0.333... == 1/3. I think 0.333... may only be a very close numerical approximation of 1/3, ...

Ditto.

... but 1/3 cannot be expressed absolutely as a number (even assuming infinite 3s).

It can be done, actually. It just cannot be done in base 10! You need to use a base that's a multiple of the prime number 3. ("trinary"?)

Re:Trinary

[Anonymous Coward]

You're just wrong.
0.333... is EXACTLY 1/3. It is not an approximation, it is the precisely same value.

And it's usually called ternary where 1/3 == 0.1 (also known as 0.333... in base 10)

Also consider that 1/2 == 0.5 (base 10) and 0.111... in base 3. So in base 3: 0.111... * 2 == 1

Face it, you just have to accept the argument.

Nice experiment you've got there....

[billstewart]

be a shame if it never finished, or took longer than the age of the universe on a computer the size of a planet before you got an answer.

You want an answer before you need to get your PhD. thesis written, maybe we can fix somethin' for you.

Re:I'll be first to say WTF

[HiThere]

I think that the elliptic cryptograms should still be valid. Unfortunately, nobody uses them because they are harder to deal with, and besides, the factoring approach got there first and seemed good enough.

(Mind you, I don't know *anything* about elliptic encryption, but at the time RSA was being first proposed as a standard, someone was claiming that elliptic encryption was what should be used, because IF P=NP, then encryption dependent on prime factorization was vulnerable.)

Re:I'll be first to say WTF

[catmistake]

Yes... Again, marketing buzzword. The universities are trying to attract tuition-paying students. Even they can't explain properly what exactly is being engineered. electrons? magnetic fields on spinning discs? Lines of code? Why not Poetry Engineers as well??

Your point taken, though... perhaps I was a bit harsh. No offense, developers!

Arrogance

[Anonymous Coward]

Anyone that thinks they know a lot is a fool.

Group Z

[gd2shoe]

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.

Sure it does, it just takes an infinite number of 0's to get there. The two are indeed infinitely close. Now for the conundrum: 0.999... is an irrational number, not an integer. 1 is an integer. Both belong to R, but only 1 belongs to Z. There may be many applications for which they are functionally equal, but they simply cannot be equivalent.

Re:Group Z

[John Hasler]

> Sure it does, it just takes an infinite number of 0's to get there.

There is no there to get to.

Re:Group Z

[Anonymous Coward]

Sure it does, it just takes an infinite number of 0's to get there. The two are indeed infinitely close. Now for the conundrum: 0.999... is an irrational number, not an integer. 1 is an integer. Both belong to R, but only 1 belongs to Z. There may be many applications for which they are functionally equal, but they simply cannot be equivalent.

There are infinite 0's, so there's no 1 to get to. And yes, it's an integer, just like 1.00 and 83/83 are.

This is one argument that is incredibly frustrating to have, because people like me who actually know their math are trying to convince the people who don't know their math (but think they do) that they're wrong. We're never going to rid ourselves of the scourge of organized religion (idiots believing in things for which there's no evidence) when people can't even accept truths that actually are proven. Humanity is screwed.

Re:I'll be first to say WTF

[TempeTerra]

Sorry to reply in an overdone subthread, but I think I have a different objection from the usual.

I'm a programmer, like many here, and I spend a lot of time working with strings, numbers and sequences. I see 0.999... as an infinite sequence which must be partially evaluated when it's used as a number. This has several consequences, but the relevant one is that when comparing numbers the obvious algorithm is to sort them by the greatest non-equal digit - so 0.999... is greater than 0.989..., and must be partially evaluated to determine that 0.9999999... is greater than 0.9999998... This understanding of 0.999... as representing an infinite sequence which can be reasoned about has worked for me in all the situations I've come across (admittedly, not many).

Of course using this reasoning also clearly tells me that trivially 0.999... < 1.

And, before someone asks, I evaluate (1/3) == 0.333... as either true based on no detectable difference, true based on a type conversion from 1/3 being identical to 0.333..., or the heat death of the universe while still looking for an answer.

Now, hopefully something interesting after another "I dun't understand math lol" post.

Obviously the 'correct' interpretation of 0.999... == 1 versus my 0.999...
< 1 is based a difference between 'real' mathematics and the bastardised computer mathematics where we don't actually have infinite sequences and have to make do, but still I can usefully define 0.999... as the largest number which is less than 1 and reason about it on that basis.

So why does 'real' mathematics use a definition based on limits rather than the shortcutty but apparently workable definition I imagine a computer using? Is there some kind of difference based on consistency of the model, or usefulness for some kinds of calculation, or just tradition or what?

P.S., sorry if slashcode ate my less than signs, I think I got them all with &lt;

Linear searches in loops

[billstewart]

My department once had a bunch of physicists writing simulation code, because some of what they were simulating behaved in physics-like ways. I was running the computer, because that was back when you often wanted Computer Nerds to do that for you, though I was really a simulation jock and math nerd.

They were in fact using linear searches through a linked list to manage their event queue in O(n^2) time, and when I made them use a heap to get O(n log n) behaviour, I was disappointed that it only sped up their system by a factor of 5; apparently their code was doing some work besides managing the event list. Also, the system they were modelling basically bounced randomly around a large matrix that didn't fit into our huge 4MB RAM (this was ~1984), and crawling through the linked lists got them some physical locality so it wasn't always paging. A couple of years into the project, memory technology and price had improved enough that we were able to upgrade the VAX to 16MB, and suddenly the program could run in an hour instead of a week, though by that time we'd been able do enough research to tell the end user that the solution we were modelling wasn't really a good one, so being able to run a few hundred more examples a week let us pile on results to help convince them.

Interesting analysis

[jd]

At the very least, then, they are saying that there are interesting subsets of the problem-space that are not truly NP but have been classed as such because the general case was.

This could lead to some very interesting consequences.

Re:I'll be first to say WTF

[Anonymous Coward]

You use the assumption you're attempting to prove in the actual proof. Surely that can't be correct?

Re:I'll be first to say WTF

[gd2shoe]

Your step 2 might be a neat trick. I can't tell because step 3 is so badly explained. Undoing the multiplication in step 1 would mean dividing by either 10, or 9.999... You cannot undo that by dividing by 9, because 9 isn't a term in that operation.

So, what exactly are you trying to do?

(I've seen nice looking proofs that 1==2. I think you're doing something odd, I just can't quite understand your operation.)

Re:I'll be first to say WTF

[HiThere]

At my university, symbolic logic was taught in the math department. There was also an "Into to symbolic logic" taught in philosophy. But they didn't even get as far as the Peano axioms, much lest second order logic.

OTOH, in the math class we needed to reconstruct Gödel's incompleteness theorem...and the lectures went on into omega incompleteness.

So, for me at least, logic *is* a part of math. (Even if most of the computer classes were oriented around numerical analysis. Well, this *was* back in the 1960's or 70's.)

Re:I'll be first to say WTF

[MooseMuffin]

The problem here is that people are generally very ill-equipped to handle the idea of infinity

Basically this. Infinity isn't a number, its an idea. If you're thinking of infinity as just some huge number, than .999... will never make sense to you.

Re:I'll be first to say WTF

[whitesea]

I don't know how you got moderated Informative; there are so many mistakes. Only RSA relies on the difficulty of factoring; ElGamal does not. It relies on discrete logarithm. Factoring is not NP-hard (neither is discrete log). Polynomial algorithm can still be sufficiently slow to be infeasible, e.g. n^100 is slow enough.

Yes, cryptography assumes that decryption is hard to do, but enough ciphers have been broken, so that we should take any unproven assumptions with a good helping of NaCl. Even if something is claimed to be provably secure, you should always check what was proven: resistance to what kind of attack is now guaranteed and under what assumptions. It's quite possible to break a provably secure cipher using a different kind of attack. For example, one-time pad is provably secure, if you never reuse it. If you reuse OTP, then your cipher can be broken (it actually happened). Also, without additional protection you may be able to change encrypted text even without being able to read it.

Please, check the statements that you post as facts.

Re:I'll be first to say WTF

[TempeTerra]

Although I am a heretic in this matter and shouldn't really weigh in; the ... operator is a mean trick which breaks the laws of arithmetic. That's why you're stumped. It's a shorthand for 'continue to infinity', and as soon as you have an infinity in your equation all bets are off.

The real kicker is that if you're not watching for that sneaky infinity it looks just like a simple equation a five year old can do.

Re:I'll be first to say WTF

[TwilightXaos]

Indeed. I meant to say

"1/3 has no exact decimal representation."

Of course meaning no exact representation as a decimal fraction

Clearly 1/3 itself is, also, an exact representation.

Implementation has terrible performance

[Anonymous Coward]

Independent of what washes out with the paper / proof...

As someone who has written SAT solvers and solves SAT instances every day... the performance of this implementation is terrible.

I was going to download it -- and then I read this on the github page:

Note that it took about 14 hours for this reference implementation to solve satisfiable 3-SAT instances with variable count = 398 and number of clauses = 1040 (flat50-115 from "Flat" Graph Colouring set).

That 14 hour instance is *ridiculously* easy... for perspective, I tried a few off-the shelf popular SAT solvers and they were all < 0.01 seconds to solve it.

Re:Implementation has terrible performance

[Anonymous Coward]

Are those off-the-shelf solvers using a probabilistic algorithm or a deterministic one; one of the key aspects of this solution is that it's entirely deterministic.

Re:I'll be first to say WTF

[Asmodae]

I don't buy it. If that were the case, then 1/3 == .333... could not exist since the division operator is broken by infinity and the equality doesn't hold, thus no arguments and we have to figure out irrational numbers all over again.

n^2 is still a polynomial, crypto's still hard

[billstewart]

Sure, there are problems that are exponentially hard that you can still often solve for small n, and there are problems that are exponentially hard in the worst case but usually only take polynomial time if you're lucky, and sometimes you can depend on usually being lucky, and there are problems that are exponentially hard if you need the best answer, but have polynomial solutions that will get you within X% of the best answer, which may be good enough.

Cryptography is not any of those problems - you can solve for small n, so the crypto designer just uses a key that's long enough not to be small, and maybe encryption takes twice as long but cracking takes 2^100 times as long. Inexact answers are good enough for the Travelling Salesman Problem, because taking 50% longer to reach all your destinations is still feasible, but guessing one bit wrong in a crypto key usually means that half the output bits are different and you don't know which ones.

Re:I'll be first to say WTF

[MooseMuffin]

Nothing, but what is the significance of there being nothing between 0.999... and 1? If there is nothing between 0.999... and 1, then you would not the logical conclusion be that there is nothing between 0.888... and 0.999..., therefore 0.888... = 0.999..., and since 0.999...... = 1 then 0.888 = 1 as well?

There's plenty of numbers (infinite) in between .888... and .999... Examples:
.9
.89
.889
.891

What would you say 1 - .999... is? If you're thinking ". an infinite number of 0s followed by a 1," there's no such thing. An infinite number of 0s has no end for you to tack a 1 onto; its just 0.

Re:I'll be first to say WTF

[Khashishi]

A number is a very specific object which differs from its symbolic representation. For example, "one", 1/1, 3-2, 0x01, "uno", 0.9999... all refer to the same real number, even though the symbolic representation is different. (However, there is also a rational number and an integer with the same symbolic name.) To show that they are the same, we need a definition of equality. Ultimately, it's a matter of consistency and convention. We have developed a framework for real numbers that gives us rules for arithmetic. The difference between 1 and 0.999... can be stated as the limit as n->infinity of 0.0...{n times}...1. However, the real number system does not allow for a distinction between infinitesimal differences, so this must be regarded as equal to 0. This is simply a feature of the real number system, so you'll end up going in circles if you look too hard for some underlying proof. In the hyperreal number system, they are different.

Re:I'll be first to say WTF

[sakielnorn]

Phew! Thank goodness I defended over the summer. Maybe I should register for a new number certifying I've read the new rules?

Re:I'll be first to say WTF

[suutar]

Well, look at it like this. Let f(x,y) = sum(n=1..x) of y/(10^n). So f(1,9) is 0.9, f(2,9) is 0.99, etc.
Using this notion, f(x,3) * 3 = f(x,9) for any x. Therefore 0.9... to x digits = 0.3... to x digits, for any x. Now set x to infinity.
Personally, I'd say that the perception that 0.9... and 1 could be different is an artifact of notation, just like a perception that 0.5 and 1/2 could be different.

Re:I'll be first to say WTF

[TempeTerra]

An infinitesmial ;)

I think it depends who you ask (I'm not a mathematician, most of my knowledge about this comes from history/philosophy of science).

Re:I'll be first to say WTF

[shutdown -p now]

I still don't see how x * 0.333... equals 0.999... (rather than 1) as x approaches 3.

This has absolutely nothing to do with "x approaching 3". We already have x=3 to begin with.

A simple explanation would be this.

0.333... = (0.3 + 0.03 + 0.003 + ...)

0.333... * 3 = (0.3 + 0.03 + 0.003 + ...) * 3

0.333... * 3 = 0.3 * 3 + 0.03 * 3 + 0.003 * 3 + ...

0.333... * 3 = 0.9 + 0.09 + 0.009 + ...

0.333... = 0.999...

Where limits come into play is for the explanation as to why 0.999... equals to 1 - as the number of digits after the decimal goes to infinity, the limit is 1. Since 0.999... by definition (of notation) is the number with infinite number of digits after the decimal point, it is 1.

Re:I'll be first to say WTF

[TempeTerra]

Well, in base 3, 0.22... == 1.

Briefly, the trick is in the ... operator, it doesn't really work like you'd expect.

(Did I miss something? The parent didn't seem particularly tied to base 10)

Re:I'll be first to say WTF

[Anonymous Coward]

I'm gonna go ahead and preorder you book now, ok?

Re:I'll be first to say WTF

[chithanh]

Actually this proof is false. In step 2, you assume that the difference between 0.999... and 1 is the same as between 10*0.999... and 10, thus making your proof circular.

Re:I'll be first to say WTF

[Anonymous Coward]

The point is that the numeral is not the number.
The numeral 0.99999... is just a silly way to represent the number that is called 1.
You are correct that in the digit representation there will always be 9s but the numeral is not the number.
Nobody ever saw a number.

As for showing that it is so just by using the numeral, I first thought of representing the number called 0.999... as:

0.999....=sum(n=1, inf) { 9 10**(-n) }
0.999....=sum(n=1, inf) { 9 exp(-n ln 10) }

but seems this discrete sum hasn't been calculated yet, just approximated. Weird. (see http://en.wikipedia.org/wiki/Exponential_sum )

Re:I'll be first to say WTF

[Anonymous Coward]

On the contrary, most crypto algorithms rely on P != NP.

Any cipher algorithms necessarily rely on this for their guarantees of security once you're beyond your unicity distance.

Checking that a key is correct (that is, including decryption) needs to be simple (P).

Finding the correct key needs to be hard - but since checking that a key is correct must be simple, it can be at hardest NP. If NP problems can be solved in polynomial time, encryption is boned if your opponent may be able to bring massively more computational power to bear than will be used to decrypt. You cannot give any strong assurances of secrecy for any messages longer than (a small multiple of the length of) your pre-shared key.

While one-time-pads remain secure due to an infinite unicity distance, they are also typically impractical - if you already have a secure channel to regularly exchange pads, then the ability to time-shift that secrecy conveys a necessarily smaller benefit than the ability to establish new secure channels.

Digital signature algorithms are even more obviously destroyed - if I can (almost) as easily find the key that produced a signature as I can check that it's valid, there's no verification to be gained from the signing process.

Re:I'll be first to say WTF

[suutar]

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.

Here's one problem. 1/3 cannot be accurately represented in a decimal system _with a finite number of digits_. 0.3 is an approximation; so are 0.333 and 0.3333333 But 0.333... is not a finite number of digits; it is an infinite number of digits, and is in fact an exact representation.

As to your questions...

1. No, just because it's infinite does not make it 1. An infinite series of 9s is not the same as an infinite series of 8s. I would however assert that 0.8... is 8/9, and 0.7.... is 7/9, and 0.34667... is 31201/90000 (there's a theme here, with the 9s in the denominator. Try the divisions for yourself if you like). Following the same pattern, 0.9.... would be 9/9, which is equal to 1.

2. In part. See 3 :)

3. The infinite nature relates to the value like so: 0.9999...99 with any finite number of digits (let's call the number of digits X) is demonstrably different from 1; just subtract it from 1 and you get 0.000....1 with (x-1) zeroes after the decimal. Try that with an infinite value for X and you never ever ever get to the 1 after the zeroes, because there is no "after the zeroes". Which leaves you with '1 - 0.9.... = 0', which (by adding 0.9... to each side) becomes '1 = 0.9...'.

Re:I'll be first to say WTF

[complete loony]

I prefer to think that 1/3 expressed as a decimal is *not* a number, but a description of a process that in some cases can only calculate an approximate value. For example when you expand the answer to 2 decimal places you get; 1/3 = 0.33 + 0.01 / 3. The notation 0.333... (usually with a dot above the last 3) suggests that you expand the answer to an infinite number of places, but even this will have a left over infinitesimal fraction.

The problem here is that decimal notation can only express the precise values of fractions if their denominator is divisible by only 2 and 5. If the denominator has any other prime factors, the value can only be approximated.

Re:I'll be first to say WTF

[chithanh]

0.999... = 1 is a convention. Whether it is true depends on how you define the real numbers. In standard analysis you have 0.999... = 1, but in other (non-standard) forms of analysis you can assume without contradiction that there is some w with 0.999... = 1 - 1/w.

Re:I'll be first to say WTF

[Anonymous Coward]

The discrete logarithm problem can be implemented via factorization and vice versa. If you can easily solve one, you can easily solve the other

That may be true, but where in your link is this stated? Closest I can see is that some discrete log solvers were inspired by algorithms for factorization, which doesn't quite mean the same thing to me.

Re:I'll be first to say WTF

[TempeTerra]

Sorry to double reply, but there's another way of looking at it I'd like to mention. I might be slightly off on the mathematics (hopefully a kind mathematician will correct me if I mess up) but it might give you another clue about how 0.99... is a special case.

Consider that for any two real numbers x and y, there are an infinite number of other real numbers z where z is between x and y. For a less algebraic example, between 0.1 and 0.2 you have 0.11, 0.12, 0.13, but also 0.111, 0.1111 and so on - an infinite number.

However, between 0.99... and 1.0 there are no more numbers. There's no way to sneak an extra digit on to the back of 0.99... to get another number between it and 1. This is obviously a very special case and for various reasons involving infinity and limits 0.99... and 1.0 are treated/defined as being the same. This might not convince you that they are the same, but hopefully it's easier to see that there's something funky going on with 0.99... even apart from saying that it's the same thing as 1.0.

Re:I'll be first to say WTF

[Khashishi]

Heh, it's not automatically obvious that "1/3 = 0.3..."
To prove it, you need to show that "1/3 = sum n=1->infinity [3*10^-n]"
Not too hard to do, if you shift the summation by one digit.
sum n=1->infinity [3*10^-n]
= {sum n=1->infinity [3*10^-n]}*10/10
= {sum n=1->infinity [3*10^-(n-1)]}/10
= {sum n=0->infinity [3*10^-n]}/10
= ({sum n=0->infinity [3*10^-n]} - 3 + 3)/10
= ({sum n=1->infinity [3*10^-n]} + 3)/10
equating the first and last expression
10*{sum n=1->infinity [3*10^-n]} = {sum n=1->infinity [3*10^-n]} + 3
9*{sum n=1->infinity [3*10^-n]} = 3
{sum n=1->infinity [3*10^-n]} = 3/9 = 1/3

Re:I'll be first to say WTF

[The_mad_linguist]

The problem here is that we never bothered choosing axioms for the discussion, and there are branches of mathematics where 0.99... != 1, which have some properties that superficially seem more intuitive.

Re:I'll be first to say WTF

[Anonymous Coward]

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

1/3 = 0.3333...
2/3 = 0.6666...
3/3 = 0.9999...

1 = 0.9999....
?

Re:I'll be first to say WTF

[Anonymous Coward]

Step 3 in the GP is a little cloudy yes, but the proof is solid. Consider the following:

1.) x * 10 = 10x

2.) 10x - x = 9x

3.) 9x / 9 = x

This is all that is happening here. Simply substitute x with 0.999...

Re:I'll be first to say WTF

[darkshadow88]

The notation 0.333... (usually with a dot above the last 3) suggests that you expand the answer to an infinite number of places, but even this will have a left over infinitesimal fraction.

No. You are expanding to an infinite number of places, so you will not have any fraction left over. You would only have some amount left over if you expanded to a finite (no matter how large) number of places and stopped.

Think of it this way: 0.333... could be thought of as an infinite number of 3's, or you could think of it as some finite number of 3's (in this case, I'm showing 3 of them), followed by infinite 3's. No matter how many 3's you conceive in the expansion of that decimal, there's still infinite 3's following them. Any amount leftover after your finite number of 3's is accounted for by the infinite 3's.

Re:I'll be first to say WTF

[TempeTerra]

Sure, so basically I agree with you. 1/3 is a ratio, and 0.333... is an inconvenient decimal representation of the same. The whole infinity and limits business annoys me when the equivalence between 1/3 and 0.33... is practically speaking a definition and 3*0.33... = 1 is an exercise in misdirection. Since when did real number multiplication involve expanding infinite series? Oh sorry, it has dots on the end. My mistake.

My beef is with the shoehorning of rational numbers into the real space; that ... operator is something you put after a real number to say "only joking! it's not a real number at all, sucker".

</rant>

Re:I'll be first to say WTF

[ittybad]

I'm sure there are already a bazillion replies to this. To prove it to myself, I did an algebraic proof. Set x = 0.999..., so 10x = 9.999..... Subtract them and get 9x = 9, or x = 1.

However, curious how my 12 year old daughter would interpret 0.999...=1, I sat that in front of her and asked what she though. She said, "nope, doesn't work." I corrected her by saying, "Ok, well, I'm gunna tell you that it is equal. Can you tell me why?" She thought for about thirty seconds and had this:

1/9 is 0.1111.... Multiply both sides by 9 and get: 1 = 0.999.... I think her answer was vastly more elegant than my own. This is like the 10th opportunity I have had to brag about this particular situation. :)

Re:I'll be first to say WTF

[Anonymous Coward]

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

Re:I'll be first to say WTF

[darkshadow88]

At any particular n, the sum is less than the fraction it represents. This the same issue for 1/3 as it is for 3/3 or 1.

Sure, as long as n is finite. The "..." at the end means it's infinite. I don't know why it's so hard for you people to grasp the idea that infinite means not finite. As soon as you think about an end to the sequence, it's not infinite anymore, and the equality does not apply. If you're having trouble with the infinite concept, think of it this way: every time you think of ending the sequence, add infinite 3s (or 9s, as the case may be).

Re:I'll be first to say WTF

[Asmodae]

You might be getting confused, but the set of real numbers includes all rational and irrational numbers. http://en.wikipedia.org/wiki/Real_number

Complex numbers are not real.

Secure channels for OTPs

[billstewart]

The secure channel for a one-time pad is a guy with a briefcase handcuffed to his arm, optionally wearing a tuxedo or a uniform or accompanied by an armed guard. Occasionally there are other options, such as a pressurized conduit between nearby buildings, with the data carried over a fiber-optic system, but that's also depending on physical security for protection.

If you've transmitted your code pad over any physically eavesdroppable medium, it's no longer a one-time pad, it's just a chunk of data encrypted with whatever encryption algorithm the transmission medium used, no matter what the sales guy for the "one-time pad" company told you.

Re:I'll be first to say WTF

[TempeTerra]

Identity is an axiom of mathematics. You have to accept it to be doing maths as we understand it, but you're free to examine mathematical systems where a != a and work with the consequences.

Re:I'll be first to say WTF

[TempeTerra]

Bugger! Catastrophic set hierarchy failure!

Thanks, I'll consider that in the morning and see if I still make any sense.

Remember kids, one little liberal arts paper might seem harmless enough but EVEN ONE can ruin your life.

Re:I'll be first to say WTF

[Anonymous Coward]

Well, it sure did wonders for teaching them how hard it is to find a route out of the building with the gun-toting maniac, didn't it?

Re:I'll be first to say WTF

[deapbluesea]

Having worked through Cook's theorem and forced to explain each and every gory detail to my professor during my oral exams, I can assure you that 3SAT is absolutely NP-Complete. What Cook did was prove by Turing reduction that all problems in P can be reduced to 3-SAT in polynomial time. Thus, if 3-SAT can be solved in polynomial time, then anything in P, to include all known NP problems, can be as well. The proof is well published and accessible to anyone with copious amounts of alcohol and pain killers. Also, a feature of NPC problems is that you can always reduce one to another in polynomial time. Other problems that have been independently shown to be NPC, such as circuit-SAT, Clique, and Vertex Cover, can all be reduced to from 3SAT. So I'm 100% confident (as in the proof covers all possibilities) that 3SAT is NPC.

Re:I'll be first to say WTF

[Anonymous Coward]

Nothing, but what is the significance of there being nothing between 0.999... and 1? If there is nothing between 0.999... and 1, then you would not the logical conclusion be that there is nothing between 0.888... and 0.999..., therefore 0.888... = 0.999..., and since 0.999...... = 1 then 0.888 = 1 as well?

0.9 is between 0.888... and 0.999...

1) If you make the assertion that 0.999... = 1, would making the assertion that 0.888... (or 0.777..., or 0.34667777..., etc.) are also 1?

No, see above. 0.9 is greater than 0.8888.... and less than 0.9999..., so they are distinct. If any two numbers are distinct, then there is something in between (e.g., their average). Therefore, if there is nothing in between, they cannot be distinct. Since there is no number which is greater than 0.9999.... and less than 1, they are exactly the same thing.

2) Is the assertion that 0.999... = 1 because of the infinite nature of a run-on number?

3) If so, why?

In a sense. The reason there is no number between 0.999... and 1 is because there are an infinite number of 9's. If there were only a finite number, we can find something in between. For instance, 0.999 != 1 because 0.9995 is greater than 0.999 and less than 1. The reason we can't do this with 0.999... is because there is no end to the nines.

(And in general I don't think there's a clear distinction between 'theoretical' and 'practical' math. 0.999... == 1 is a standard result in real analysis, which is far more 'practical' than one might imagine after taking a first course. Are you doing any numerical work with non-integers? If you want to be sure your method converges to the right solution every time, you're probably going to have to bring in real analysis.)

Re:I'll be first to say WTF

[darkshadow88]

Only if by "non-standard", you mean "wrong".

Re:I'll be first to say WTF

[Jessta]

Your understanding of infinite is flawed.
"the end of all those infinite 9s"? what end? it's infinite.
infinite doesn't just mean really, really, really big. it's infinite, it has no end.

Re:I'll be first to say WTF

[Alarindris]

What the hell is insider baseball?? He keeps using that term but never explains what it means. Renders the article unintelligible, to me, anyway.

Re:I'll be first to say WTF

[SanityInAnarchy]

Again, marketing buzzword.

Apparently you missed the part where there's an entirely different focus. Computer Science focuses more on math, abstract ideas, and programming itself. Software Engineering seems to focus more on process, design, and generally management ideas.

Even they can't explain properly what exactly is being engineered.

...so, how's this different than Computer Science?

electrons? magnetic fields on spinning discs? Lines of code?

Electrons and magnetic fields are building blocks. Here, let me turn it around for you:

Even they can't explain properly what exactly is being engineered. Steel? Concrete? Bridges?

One of these things is not like the other...

To answer your question more directly, a running program is the end result that people are interested in. The intermediate stages are lines of code. These are pretty directly analogous to an airplane being the end result, and drawings, streamlines, and so on all being things the engineers may or may not have to work with to achieve that final result.

If your issue is with the word "Engineer", I'd like to hear your suggestion for a better word. Problem is, "Developer" and "Programmer" have pretty much identical meanings, neither of which implies any experience designing processes or working with algorithms and theorems.

And why not Poetry Engineers? Think about what that would imply. A poetry engineer would make sense if you wanted a poem to have a specific effect. If there were well-understood principles by which you could design a poem such that everyone who read it would reliably experience the precise emotion you intended, then there would be poetry engineers, and they would be highly paid, I would think.

How about a "hair style engineer"? From Wikipedia:

Engineering is the discipline, art, and profession of acquiring and applying scientific, mathematical, economic, social, and practical knowledge to design and build structures, machines, devices, systems, materials and processes that safely realize solutions to the needs of society.

That seems to apply to software. It does not seem to apply to hairstyling.

Now, don't get me wrong, there's plenty of people who manage to get through a comp sci program without really learning much, and I'd think that especially depends on the school. There are PhDs who are so out of touch with the act of programming itself, so lost in theory, that I've seen a group of high school graduates (might even have been some dropouts) run circles around them, doing things they dismissed as "impossible" in an afternoon. If I ever do go to graduate school, I don't really intend to become a sanctimonious asshole with a Dr in front of my name.

But the fact that these degrees are sometimes ineffective and abused doesn't rob them of their meaning, or render them mere buzzwords.

For what it's worth, I'm working on a Computer Science degree, mostly because it gives me time to dabble in other things like philosophy courses and martial arts.

Re:I'll be first to say WTF

[Cinder6]

Whoosh? Or maybe I'm just not funny.

Re:I'll be first to say WTF

[barrtender]

That doesn't really make sense. You can hand someone a bunch of one-time pads before they go somewhere. You can't hand them future messages beforehand (or maybe I missed some neat trick in the article).

Re:I'll be first to say WTF

[LrdDimwit]

Alright, see if you find this proof convincing.

1) .9999... is clearly not greater than 1.000.... Therefore 1.000... - .999... is clearly non-negative

2) What IS .999...? Well, it's greater than .9, and it's also greater than .99, and it's also greater than .999. More generally, for any finite sequence of nines S9 after the decimal, .999... is strictly greater than S9.

3) If a > b, then c-b > c-a. Thus, given 2), for ANY finite sequence of nines S9, we see that 1.0 - S9 > 1.0 - .999...

4) What do we know about 1.0 - S9? Well, as the number of 9's after the decimal approaches infinity, S9 converges to 1. This means that 1.0 - S9 converges to 0. Among other things, one of the things that this means is that given any positive number epsilon, no matter how small it is, we can force 1.0 - S9 to be smaller than epsilon.

5) By 3) and 4), we conclude that 1.0 - .999... is less than ANY positive real number. By 1), we conclude 1.0 - .999... is nonnegative. Therefore, 1.0 - .999... is equal to zero -- another way of saying .999... is equal to 1.

Re:I'll be first to say WTF

[ajs]

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

That's not always practical. All secure channels I know of rely on either very close proximity or tremendously expensive physical security. As such, secure channels tend to be limited, while the locations from which one wants to send a secure message are numerous. Therefore, it makes sense to physically go to a secure channel, get a one-time-pad and then, when you need to communication, use it to send your message from anywhere, over an insecure channel.

Romanov huh...

[Anonymous Coward]

Heh. Who knows what his uncle Nicholas and his cousins Anastasia and Alexei could have done had not the bloody commies killed them in 1918...

Re:I'll be first to say WTF

[Anonymous Coward]

You can give all manner of proofs that 1=.999999..., but they tend to involve symbolic manipulations of some sort, and while they layperson might feel that each individual step *seems* justified, they will be convinced that there is some sort of sophistry involved, and that one of the steps isn't quite right. The issue is that they don't really know the difference between a number and a decimal expansion. One is a representation of the other, but they are not the same. The following example is useful for showing the difference between a number and its representation.

Consider the following way of representing a positive integer, based on the fibonacci sequence, 1, 1, 2, 3, 5, 8, ...., where we denote the nth term of the sequence by f_n. We take a finite string of 0's and 1's of the form (a_n)(a_n-1)...(a_2)(a_1) and say that it represents the number a_n * f_n + a_n-1 * f_n-1 + .... + a_2 * f_2 +a_1 * f_1. For example 1011 represents 3+1+1=5, as does 10000. We see that numbers do not have unique representations in this form. However, they do have unique representations where there are no consecutive 1's.

We can contrast this to base 2 representations of integers, where every number has a unique representation as a string of 0's and 1's, or base 10, where every integer has a unique expression as a string of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Actually, these expansions are not quite unique, as we have to restrict to strings that do not start with 0.

When people think about numbers bigger than 10, they tend not to think of them as an abstract quantity, but rather as a decimal representation. This works well enough, because representations are essentially unique. But people still understand what an integer is, and nobody confuses the decimal expansion of 12 with the fact that you can count out a dozen eggs one at a time.

However, there is a disconnect between numbers and their decimal expansions when they are not integers. Why is 1/3=.3333333...? People might be able to say something about the division algorithm, and how if you divide 1 by 3, things never stop and you keep on getting 3's. But what does .333333.... mean, in the absence of actually doing division? And given that no division will ever actually give you .99999999....., what does that mean?

The answer is that decimal expansions are shorthand for saying that we can get successively better approximations to our number by taking more and more digits. If we don't assume that everything has a unique decimal expansion, and that decimal expansions just represent numbers, the answer isn't mysterious. Does .99999.... = 1? That's just the same as saying "Does taking more and more digits give us arbitrarily good approximations of 1?" Taking n digits approximates 1 to within 1/10^n, which approaches 0, and so the approximations get arbitrarily good, and hence we do have equality.

Re:I'll be first to say WTF

[John Hasler]

Well, you wouldn't have to put up with my cheap shots and snarky comments...

Re:I'll be first to say WTF

[billstewart]

R's a pretty schmart guy, and while I haven't mean S or A, I'd bet that's true about them as well.

N = PQ, where P and Q are primes. If you know P and Q, you can determine the encryption and decryption keys in polynomial time, and use them in polynomial time, which is why using RSA at all is practical. If an oracle gives you p and q, you can determine in polynomial time whether N = pq, therefore RSA is in NP. The best-known algorithms for factoring are around e^(n/3), which means that you can make it the work your attacker needs to do exceed the predicted lifetime of your planet while still only needing to do small amounts of work yourself, so that means that RSA provides security while remaining practical.

If P=NP, then there is an algorithm to determine P and Q from N in polynomial time, and therefore an attacker can determine your keys in polynomial time, so you're not secure. It may be that the polynomial is something large and annoying, like O(N^10) to crack vs. O(N^4) to generate keys, in which case a defender with moderate resources might still be able to protect her data against an attacker with relatively large resources, but it's more likely that a defender wouldn't be able to create practical-sized keys with age-of-the-planet attack times.

Factoring is not believed to be NP-complete, so it's possible that somebody could solve factoring without solving 3-SAT, but this guy's apparently claiming to be able to solve 3-SAT, at least to accuracy-of-the-media levels of interestingness.

Re:I'll be first to say WTF

[ajs]

there's a 9 at the end

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

Correct.

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.

I'm not sure that I buy that 0.333 repeating added to itself three times is 0.999 repeating. In fact, I'm not sure that I fully understand what addition means when you involve the decimal representation of a repeating fraction. I intuitively know the result because I convert this to 1/3+1/3+1/3 in my head, but how do I determine if there's a carry operation when doing this in decimal?

Re:I'll be first to say WTF

[Anonymous Coward]

Not all geeks are computer scientists. I'm an aerospace engineer and I got my card in no time.

Re:I'll be first to say WTF

[Surt]

Exactly. The security of RSA has nothing to do with p/np but with the lack of an efficient algorithm for factoring. p=np only proves an efficient algorithm exists, but doesn't supply it. It could be many, many years (or never!) after p=np that such an algorithm is discovered.

Do Non-Deterministic Turing Machines exist?

[billstewart]

To be precise, probably nobody's built one on purpose...

If you're asking whether non-determinism exists in the physical world, that's really a metaphysical question, and you should ask a philosopher or your local quantum mechanic. In the cryptography business, the closest related problem is "If you've stolen a key from your target, can you tell if it's the right one?"

The original Turing machines had infinitely long tapes, which is easy to do if you don't have to build one of them. Since the original work in NP-Completeness, there have been a bunch of further problem classes defined that may constrain the size of the Turing machine, e.g. PSPACE problems with can only be run on a system with space that's bounded by a polynomial function of the size of the problem, so you potentially could build them for some reasonable sets of problems. More years, more PhD theses, more professors needing to publish papers, more problem categories.

Re:I'll be first to say WTF

[treeves]

What do you know about number theory? Aren't you some kind of expert in non-Euclidean geometry?

Re:I'll be first to say WTF

[Lobachevsky]

Exactly - it's a very common epsilon-delta proof. You challenge the opponent to find an epsilon they think your answer is wrong by, and you come up with a delta that beats your opponent's epsilon. In formal terms, (f(x) - f(x+delta)) epsilon. In this case, f(x), the target is 1, and delta is -epsilon. If your opponent challenges you to find a number 0.0001 close to 1, you can give him 1-0.0001 (aka 0.9999). Because your opponent can pick arbitrarily close to 0, and you always have a delta to win the challenge, then your opponent cannot claim your number is any different from 1.

Re:I'll be first to say WTF

[Anonymous Coward]

Correction. It does not take exponential time to factor a product of two large primes. The general number field sieve is sub-exponential, though it is super-polynomial. See http://en.wikipedia.org/wiki/General_number_field_sieve for details.

Re:I'll be first to say WTF

[caerwyn]

Really? I haven't encounter any of those; can you provide any more information?

Of course 3-SAT is NP-complete, but then what?

[billstewart]

If you're working in a given field, there may be problems that are more like the one you're working on than 3-SAT, so you can reduce to/from them, which will often be much easier and more efficient to prove, even if it's a less efficient way to solve 3-SAT. If your goal is theoretical, that's fine - Reduce FOO to BAR, BAR is known to be NP-Complete, Deliver Thesis.

If your goal is practical, because you want to solve real instances of FOO, tell you it's NP-hard may say you shouldn't try to find the optimal solution but look for near-optimal heuristics, or maybe you should reduce it to BAR, which already has a good near-optimal heuristic or has an optimal solution that's usually but not always fast. Or it may be that knowing that FOO is NP-hard tells you to give up and solve a different problem instead (e.g. in cryptography, where inexact solutions are useless so maybe you should put a keylogger in your enemy's keyboard or drug the courier who's got the one-time pads instead.)

Re:I'll be first to say WTF

[complete loony]

I believe the worst problem with recurring decimal notation is dropping the implied remainder. My point was that the expansion of 1/3 to any finite number of decimal points always has an implied fractional remainder that is usually not written down. Each step of the expansion process to another digit reduces but does not eliminate the remainder. Therefore, even if you continue this expansion to infinity, the remainder in your calculation never disappears. Even if its limit approaches zero, it is *not* zero.

Re:I'll be first to say WTF

[Dwonis]

Well, no. In ALL cases where f(x) exists, the limit of n as n approaches x is ALWAYS f(x). It is the same thing.

Only if f(x) is continuous.

Re:I'll be first to say WTF

[catmistake]

I also studied TRUE Computer Science (subset of math... hell... it was all math), though I do not work as a scientist... I am a practitioner. I know what science is and I know what it is not. My issue is with the word "engineering." Bridges and roads and even computers ARE engineered. They are tangible, physical, REAL. Software is called SOFTware for a reason. You can't actually SEE it (the thing in itself), SMELL it, TASTE it or TOUCH it, or HEAR it, or empirically sense it it any way other than it's effects (a blip on the screen); software is conceptual. Engineering is not conceptual, it is always quite tangible. I think your examination of my example of poetry and hairstyling engineers is quite arbitrary. I'm not saying that what they want to call software engineering isn't science... just that it isn't engineering, in the same sense that a journalist isn't a news engineer. It dilutes the meaning of the word, your wiki definition notwithstanding. Prior to about 1995, there was no such term as a software engineer, yet there were certainly the same tasks being delt with to a large extent for at least the previous 30 years, if not the previous 6000 years. Even the work of a poet can withstand a large electro-magnetic pulse, either in our memory or in a printed piece of dead tree, so in a sense, a poem is far more "real" than a computer program. If you build a bridge, no matter how terrible it is, no matter how little planning you put into it, you still engineered it, because it physically exists, after all. A mathematical equation, on the other hand, can't truly be engineered. Philosophically speaking, that equation existed a priori, like all numbers, simple or complex, without the need for any anthropomorphic realization. There are no software engineers in the same sence that there are no mathematical engineers. This term was applied as a marketing device. Software Engineers ARE Software Developers with a cooler name. Marketing, nothing more.

I wish you luck with your studies. Computer Science is a cold unforgiving bitch, a true moving target of a curriculum if ever there was one.

Re:I'll be first to say WTF

[KZigurs]

But it is :)

Re:I'll be first to say WTF

[Anonymous Coward]

I am confused. Which step is profit?

Re:I'll be first to say WTF

[Missing.Matter]

Blizzard, the entertainment company? Is it part of some kind of joke? Obviously I'm missing something when someone cites an entertainment company for a mathematical proof.

Re:I'll be first to say WTF

[KZigurs]

How many crayons he has?

Re:I'll be first to say WTF

[Dwonis]

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

Really? What algorithm did you use to get that? The algorithm they teach in school involves starting at the rightmost non-zero decimal place of both terms, but neither 9.999... nor 0.999... have rightmost non-zero decimal places.

Your multiplication step in #1 has a simiiar problem.

See also Mathematical fallacy - Infinite series on Wikipedia.

Re:I'll be first to say WTF

[williamhb]

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.

More to the point, what you are effectively saying with the "..." in 0.999... is
Lim[n->infinity] Sum[m - 1 .. n] (9 * 10 ^ -m)
and the result of that limit equation turns out to be 1.

Re:I'll be first to say WTF

[Cinder6]

Yes, that Blizzard. It was an April Fools' joke, but it's still valid.

Re:I'll be first to say WTF

[KZigurs]

Pah, brute force is P although the problem moves over to defining the input set.

Re:I'll be first to say WTF

[Anonymous Coward]

More to the point, what you are effectively saying with the "..." in 0.999... is
Lim[n->infinity] Sum[m <- 1 .. n] (9 * 10 ^ -m)
and the result of that limit equation turns out to be 1.

(pardon the missing < -- slashdot gobbled it up)

Re:I'll be first to say WTF

[arodland]

If 0.999... != 1, then there exists a number which is greater than 0.999... and less than 1. What is this number?

Re:I'll be first to say WTF

[Whomp-Ass]

Well, duh, when you break that 1 into 3 parts you're going to miss a few crumbs here and there, you know, onto the floor, stuck to whatever you cut that one up with...I mean, why get so worked up over a crummy unit?

Re:I'll be first to say WTF

[JesseMcDonald]

The problem with that approach is that it's circular: it's true if 0.999... is exactly equal to one, but false if it's only an approximation:

Let x = 0.999...9 (any finite number of 9's);
then 10x - x = 9x = 8.999...1.
Dividing both sides by 9, x = 0.999...9 != 1.

Re:I'll be first to say WTF

[Cinder6]

Yeah, but since neither I (or the random Blizzard "press release" I found) are using approximations, then it's true.

Re:I'll be first to say WTF

[KZigurs]

And then there are those who settle on sub-par supplies too, of course.

Re:I'll be first to say WTF

[Seth024]

And in base 3:
0.0222... is 0.1

Re:I'll be first to say WTF

[jvonk]

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

Re:I'll be first to say WTF

[emt377]

I think 0.333... may only be a very close numerical approximation of 1/3

It's not. 0.333... isn't a number at all, it's a summation series of infinite length. That means it never ends. Ever. It's another exact way of stating 1/3. "0.3333" or any other finite series would be an approximation.

It's just like you can state cos(x) = 1-(x^2/2!)+(x^4/4!)+... This is an exact definition, not an approximation. If you want to say integrate cosines, or square the cosine, then you can derive another exact definition for the integral or square. In the case of the integral you might recognize that it can be refactored in terms of the series for the natural logarithm; the infinite series is a very useful analytical tool. And it's used to deal with exact definitions, not approximations.

WTF

[mestar]

"including one that runs in time (4/3)^n and succeeds with high probability."

I'll create one that runs in O(1) time and succeeds with very low probability.

Re:WTF

[zarzu]

you might be interested in monte carlo algorithms.

Infinite series and continuum

[gd2shoe]

Oh ye of little faith. Bear with me as I show you how.

Imagine an infinite series of pairs. Let's start with .9 and .1. This pair total 1. The next pair in the series is .99 and .01. It also totals 1. Following that is .999 and .001, and so forth. As the number of 9's increases, so too does the number of zeros. But there must always a 1 on the end. It is vital for the series to be correct. You can't just assume that it goes away as you approach infinity; it's part of the definition of the series. If you have infinite 9's, than it must be paired with [infinity-1] 0's and a 1, and together will total 1.

If a solitary 1 at the end of infinite 0's is impossible, then so too is an infinite number of 9's. They are opposite sides of the very same coin.

Another way to think about this: we're talking about the set of real numbers. This set is a continuum. In other words, between any two points lie an infinite number of other points. This must mean that some points are infinity close to each other. It's just the nature of the thing. 0.000...0001 is just such a number. It is infinitely close to 1, but not equal to it. There must be such a number, or there could be no continuum. The set of real numbers could not be.

A mathematician would surely say it's much more complicated than that, but you get the idea.

Re:Infinite series and continuum

[masterzora]

It's actually much less complicated than that. The process you're proposing can't actually be done. Not only that, but 0.999999... is *not* a process; it simply is. I understand that infinity is hard to wrap your head around, but the first thing you need to understand is that there is simply no process here. That's one of the things that really pisses constructionists off, which just means it amuses me more.

Re:Infinite series and continuum

[gd2shoe]

Oh, get off your high horse. That's just the high brow version of school yard taunting.

Take for a moment that I'm wrong. I don't think that I am, but I'll concede the vague possibility. (I have been before.) Your words teach me nothing. They convince me of nothing. They provide no intellectual sustenance. They are a rebuke, but not a rebuttal.

Sorry, no. I'm not going to simply take your word for it. (Not that this is important or anything.)

Re:Infinite series and continuum

[masterzora]

Who said I was doing anything more than a rebuke? It is clear that you don't understand the nature of real numbers, nor the nature of infinity. This left me with three choices: Be the one to try to teach you these fundamental concepts, don't comment at all, or take my time to poke some fun. By the way I derided constructionists at the end, I thought it would be clear that I was just being an ass.

Though, if you seriously do want some education, here's a few things to think about:
* 0.999... is not a process. It is simply a number.
* While it is just a number, 0.999... can be constructed from a process. Specifically, \sum_{i=0}^\infty 9/10^i.
* There is no analogous process for producing what you call "0.000..0001", nor does this concept mathematically make sense. The closest concept is lim_{n\rightarrow\infty} 1/10^n, but this is 0, not some mystical 0.000..0001.

The point is, as I've said multiple times already, a number is not a process. This is key to understanding why .999... and 1 are not distinct.

Another important thing to understand is that any numerical representation must have multiple representations for the same number. It is no stranger that .999...=1 than it is that 1 = 1.0 = 1.00...

Finally, one last thought to leave you with: you are proposing a number that would necessarily be the smallest possible positive real number. However, it would immediately follow that the real numbers would be countable, via an obvious bijection with the natural numbers (specifically, your 0.00...001 would match 1, 0.00...002 would be 2, and, in general, you would match n with 0.00...001 * n). However, it's already been proven to death that the real numbers are uncountable. Therefore your number cannot exist.

Honestly, though, when it comes to it, I can prove it rigorously many different ways, most of which you likely don't have the mathematical background for if you still believe .999... != 1, and you're going to continue to trust your intuition, thinking that we must be tricking you or something. Which is why I didn't even bother the first time around.

Re:I'll be first to say WTF

[Burz]

They may both be fine for representing the same physical amount, but 0.999... and 1 differ as numbers in a very obvious way: The former repeats endlessly while the latter is static and has a completely stable meaning.

Re:I'll be first to say WTF

[gd2shoe]

Says AC who refuses to provide such a derivation. I can also derive 1=2. That doesn't make it true. (1==1/0==0; also "provable"; also not true.)

Show it, or shut it.

Re:I'll be first to say WTF

[Matrix14]

Yes it does. The two formulations are equivalent, and, in fact the time-to-check answer one is much more commonly used because it is much easier to reason about.

Re:I'll be first to say WTF

[Puff_Of_Hot_Air]

I think the issue is with the explanation of "recurring". 1/3 is not 0.333333 written forever. 1/3 is the _limit_ of 0.333333. It's what you get when you reach the edge. Hence calculus. 0.9999 recurring is the same. If you think "it's writing infinite 9's" then you've missed the point. 1 is the _limit_ of writing infinite 9's. It's what you get when your done.

Re:I'll be first to say WTF

[Anonymous Coward]

I do have an issue with this proof, and I believe the assumption in (1) is incorrect.
By assuming in your premise that (0.9999.... * 9) - 0.9999.... = 9, you've already made the assumption that 0.9999.... = 1

Suppose 0.9999... may not be 1. Suppose 0.9999.... = 1 - x, where x is some value:

1) 0.9999.... * 10 = (1-x) * 10 = 10 - 10x

2) (10 - 10x) - 0.9990.... = (10-10x) - (1-x) = 9 - 9x

3) (9-9x)/9 = 1-x (aka nothing has changed, and nothing has been proven by this sequence of toggling).

A correct proof would show definitively that x = 0. Which is not possible. You can only show that x --> 0 (which is true IMHO).
Because 0.9999..... != 1. 0.9999.... --> 1

Re:I'll be first to say WTF

[Anonymous Coward]

Didn't see any algebra in your proof. I think you meant to do something like

x = .9...
10*x = 10*.9...
10x = 9.9...
10x -x = 9.9... -.9...
9x = 9
x = 9/9
x = 1
x = .9... = 1

Or I'm just being pedantic about the use of the word algebra.

Re:I'll be first to say WTF

[Anonymous Coward]

Just to be more verbose, basically, suppose that 0.9999.... = 1-x

x may be zero or not. Which is what we need to determine.

now 0.9999.... * 10 = (1-x) * 10 = 10 - 10x
However the proof supposes without hard evidence that 0.9999.... * 10 = 9.9999.... , which is being treated as 10 - x.

Hence the proof supposes without hard evidence that 10 - x = 10 - 10x. Following this, its not hard to "arrive at the conclusion via arithmetic" that x = 0.

Re:I'll be first to say WTF

[itslifejimbutnotaswe]

Simple: 0.333... = 0.3 + 0.03 + 0.003 + ... = 3 (0.1 + 0.01 + 0.001 + ...) = limit 3*sum(10^-n). The infinite sum converges to 1/9, which exists as a real. Multiplying by 3 gives 1/3. Multiplying the whole thing by another 3 gives 1. The term-by-term multiplication is valid as the series is convergent.

Re:I'll be first to say WTF

[H0p313ss]

If your system has a fixed amount of memory, then I suggest that they really added O(1) to your projects

Does anybody still write simple numerical problems like that anymore? I have not done anything that trivial in over a decade and a half.

Re:I'll be first to say WTF

[itslifejimbutnotaswe]

Or you could use 1/7 = 0.142857142857... Or 1/11 = 0.090909090909... From here you can probably convince them that ANY rational can be written exactly as a recurring decimal (as 10^k-1 is divisible by k for all k)...

Re:I'll be first to say WTF

[itslifejimbutnotaswe]

Or you could use 1/7 = 0.142857142857... Or 1/11 = 0.090909090909... From here you can probably convince them that ANY rational can be written exactly as a recurring decimal (as 10^k-1 is divisible by k for all k)...

Doh, that's not quite right, but you get the idea.

Re:I'll be first to say WTF

[itslifejimbutnotaswe]

Ah - it's got a pigeonhole principle thing happening: the remainder when dividing 10^j by k for j = 1..k must either repeat or be zero. See what fun one can have with such "simple" problems.

Re:I'll be first to say WTF

[jellyfrog]

http://qntm.org/pointnine

Analogies sometimes make understanding harder

[snowwrestler]

I know you've gotten a ton of other answers, but I think your fundamental difficulty is in the analogy you're trying to employ.

0.999... is not a equation or sum approaching a limit, it is a single number. The fact that we read left to right does not mean that there is any actual evaluation happening as our eyes drift down that long, long row of 9's. Each 9 is not a subsequent point on a line that is approaching an asymptote. The entirety of (0.99... ) represents, itself, a single point on the line of the reals. That point is infinitely close to 1, and is stationary...it's not "approaching" 1, it's already there and it's sitting right on top of it. It's the same point.

Hopefully this geometric analogy will help. ;-)

Re:I'll be first to say WTF

[snowwrestler]

A number written like 0.99... does not have a right edge. The 9's continue forever.

Re:I'll be first to say WTF

[snowwrestler]

No, this is incorrect, only equations and sums approach limits.

The series 0.9 + 0.09 + 0.009 + .... approaches a limit.

0.99999... is a number. It does not approach anything, it simply is. It just happens to be a number that looks messy in our decimal notation.

Re:I'll be first to say WTF

[darkshadow88]

The problem is that you're thinking of it as a process of adding digits to the end, rather than the infinite digits that are just there in the decimal representation. No matter how long you continue the "expansion process" for a finite number of steps, you will not get rid of the remainder. The whole point of having infinite 3s on the decimal representation of 1/3 is that no finite number of 3s would be exact.

Infinity is a hard concept for many people to grasp. As soon as you understand that infinity does not mean "a really large number" or even "as far as you could count if you started from the start of the universe and continued until its eventual destruction", you'll understand why 0.999...=1.

Re:I'll be first to say WTF

[deapbluesea]

Not even close. Brute forcing a password of fixed size n will be k^n where k is the number of possible characters. A polynomial increase would be n^k with k being some constant. If brute force search were in P, then all answers would be achievable in polynomial time, to include answers to NP problems (which are verifiable in polynomial time), thus 2*n^k which is still polynomial and would trivially prove P==NP if it were true.

Re:I'll be first to say WTF

[Durandal64]

You can represent the same number with different glyphs. It's better said that 1 and 0.999... represent the same number. Just like how 1/3 and 0.333... are different representations of the same number. Or how 1000 and 8 are different representations of the same number.

Numbers are abstract concepts. We represent them with a standardized system, sure. But at the end of the day, we can represent them however we want. It just happens that the most useful representation is a standardized one.

Re:I'll be first to say WTF

[Nux'd]

To say that 0.999... = 1 is undeniably the case is just not true.

It's quite possible to define a number system that has numbers separated by an infinitely small gap just as much as you can have numbers so large they can only be expressed as bigger than all numbers of a set. It's still maths and it still produces true statements.

Maths will only ever churn out true statements based on the assumptions you make, it's your philosophy that will tell you what assumptions are meaningful.

Re:I'll be first to say WTF

[Darinbob]

My point is that all your algorithms are theoretically O(1) if "n" is not unbounded. Ie, if you only have 64K of memory. Remember that O(1) is the same as O(100000000000).

Granted this is technical nit-picking, but it's an important point when working with the theory.

Or as one of my colleagues in grad school used to joke that all functions can be reduced to table look up. Just when you thought you understood Big-Oh for time, now you've got to work with Big-Oh for both time and space.

The title

[Anonymous Coward]

"==" usually means "test whether both sides equal" whereas "=" means things on both sides really do equal.

It irks me that people tend to think == means that things equal; more equal signs does not make the statement more valid, on the contrary, it makes one question the validity in a way..

Re:I'll be first to say WTF

[i_liek_turtles]

Any rational can be expressed by its terminating decimal notation (if it has one) and its repeating decimal notation

ok the easy version

[tempest69]

Assertion to be tested
.999... = 1

Rationale:
because 10 X .999... = 9.999...
9.999... - .999... = 9.000... ((10-1)*.999)
so 9 times .999 is equal to 9.000...
so 9.000... /9 = 1.000...
so .999 is = 1.000...
so either (1.000... is not equal to 1) or (.999... is equal to 1). So math goes with the second.

Re:I'll be first to say WTF

[i_liek_turtles]

You can express it as an infinite geometric sum (0.9+.09+.009+...+9/10^(-n)) that converges at one

Re:I'll be first to say WTF

[Anonymous Coward]

Meanwhile, NP looks at the mirror and at her golden globe and says... You think P is enough? only if you say it about b^n times. Better luck next time!

Re:I'll be first to say WTF

[Anonymous Coward]

As long as the debate as to whether Gork or Mork is better.

Re:I'll be first to say WTF

[Ihmhi]

Hey man, thanks! I think I have a pretty good handle on things now.

Re:I'll be first to say WTF

[Anonymous Coward]

That last bit is fun to read aloud: .... the hardest ones in in pea, in the sense that if any of them is in pea, then everything in in pea is in pea .... ;)

Re:I'll be first to say WTF

[masterzora]

NOTE: Yes, I use a few simplifications and a lot of non-rigorous language. This should still be good enough to give the basic idea to people who don't study complexity.

What other option is there? It's either polynomial (P) or not polynomial (NP), isn't it?

Your first problem: NP does *not* mean "not polynomial" or even anything remotely like that. It means "non-deterministic polynomial time", which essentially means we can verify the answer in polynomial time. All P algorithms are inherently also NP. NP-complete problems, like 3-SAT, are problems such that it is easy (i.e. doable in polynomial time) to turn any other NP problem into them. That's why being able to solve an NP-complete problem in polynomial time means we can solve all NP problems in polynomial time. NP-hard is another class that only partially overlaps NP, and it means that the problem is at least as hard as the hardest problem in NP (i.e. it may or may not be in NP, but it's at least as hard as an NP-complete problem).

Note, there are many, many more complexity classes than just these, also. NP is just the set of yes/no problems that can be verified in polynomial time. One thing you'll note is that integer factorization isn't in NP. Or, more accurately, integer factorization as you usually think about it isn't in NP. The "decision version" (i.e. NP version) of the problem is, essentially, "Is there a non-trivial factor of a given number?" The analogous "function version" is much more what you probably consider to be integer factorization: "Is there a non-trivial factor? If so, give me one." Function problems exist in a different class: FNP, which has FP as the counterpart to P. However, FNP=FP if and only if NP=P.

And, just for your edumacation, a small sampling of other complexity classes:
* PSPACE (doesn't care about time; it's the set of problems that can be solved with polynomial _space_; note that we've already proven that the analogous "NPSPACE" is equivalent to PSPACE; we've also shown that NP is entirely contained within, but not equivalent to PSPACE)
* BQP (similar to P, except with quantum computers and a hint of uncertainty; in particular, it's the set of decision problems solvable on a quantum computer in polynomial time with the kicker that it allows for a limited probability of error; we don't know how this relates to NP, other than that all P problems are BQP)

There are many, many others, covering far more things than you can probably imagine without a background in complexity.

Anyway, that was a bit more teach-y than I had expected, but complexity is one of those topics that I adore too much to pass up such an opportunity.

Re:I'll be first to say WTF

[Anonymous Coward]

In mathematics, italics are generally used for definitions and not for emphasis. That seems to be the case here -- he's "defining" what he means for substructures to be processed in parallel. I'm rather impressed that you made it that far through the paper. I'd dismissed it as crankery before the end of page 1 and moved on with my life.

Re:I'll be first to say WTF

[Anonymous Coward]

Rational numbers vibrate/oscillate. Probably transcendental ones too!

Re:I'll be first to say WTF

[TechyImmigrant]

hexadecimal.

0.999... != 1
0.999... = A

Re:I'll be first to say WTF

[masterzora]

And you're wrong in a very obvious way: 0.999.... is every bit as static and stable as 1, even if they were not equal (the same way that 0.333... is static and has a stable meaning). The fact that we are using an infinite number of digits to represent it in decimal does not change this fact. Numbers are not processes. If they were, then in order to cut .333... of a cake I'd need to go 3/10 from my first cut, then 3/100, then 3/1000, etc forever. You can do that if you want, but I''ll just go .333... from the outset and be done with it.

Re:I'll be first to say WTF

[TechyImmigrant]

Obviously I meant .A, not A.

Re:I'll be first to say WTF

[Anonymous Coward]

That is wrong. In all cases where F(x) is CONTINUOUS near x0 the limit of f(x) when x -> x0 is equal to f(x0).

That is wrong as well. If F(x) is continuous at (not "near") x0, then F(x) -> F(x0) as x -> x0.

Re:I'll be first to say WTF

[complete loony]

I did mean to suggest that I don't understand the common definition of 0.999...=1, I understand the notation. It was this very definition of 1/3 = 0.333... I was arguing against because I believe that 0.333... with an infinite number of 3's is a useless concept. The action of writing out 1/3 in decimal notation is a process, as is the process of writing out the first 1 trillion decimal digits to pi. Both are numbers that decimal notation cannot accurately represent as neither number can be expressed precisely as a fraction with denominator divisible by only 2's and 5's. I was simply stating my belief that it is misleading to simply say that these digits continue to infinity, instead of leaving an explicit remainder or error bounds information from such a representation.

Re:I'll be first to say WTF

[Garridan]

Traditional usage of the one-time-pad is to bring a book of pads. When you write back home, you use a pad and send the encrypted message over any channel available. When home writes back, they encrypt their messages with pads that you've got with you. When you finish using either, you burn the page that the pad was on. The pad is never transmitted. The agent receives the pad book directly from the person they wish to communicate with, and absolutely nobody else is allowed near the twin.

Re:I'll be first to say WTF

[kylemonger]

Proving P=NP by (for example) finding a polynomial time solution to a #P-complete problem won't immediately kill RSA because it's unclear (to me at least) how that would map to an efficient factoring algorithm. But a constructive proof such as what Romanov claims, i.e. an efficient 3-SAT solver, immediately deals a death blow to RSA, AES and everything else but one-time pads. That's because all these systems are polynomial time reducible to some 3-SAT instance.

Re:I'll be first to say WTF

[masterzora]

You're forgetting the second part of this: because NP-completeness proofs have formed a chain of reductions, finding an algorithm for one of them is the last step to finding an algorithm for all NP-complete problems that we have found (and any others we manage to reduce later).

Re:I'll be first to say WTF

[Anonymous Coward]

No, but I read the article.

*ducks*

Re:I'll be first to say WTF

[Anonymous Coward]

Zeno needed here:

Suppose you want to recite Pi to your buddies, but you don't have all day. Since you are Superman, you decide to start out at normal speed, but then cut the time it takes to recite each subsequent number in half because you remember from reciting 1/7 you could finish is a surprisingly short period of time. Surprisingly, you find out that it doesn't work like you did when you recited 1/7. You give up and decide you aren't so super after all. What went wrong?

Re:I'll be first to say WTF

[H0p313ss]

Given that these days were working with gigabytes of memory I really don't want to encourage anyone to consider such folly for enterprise scale applications and services.

Re:I'll be first to say WTF

[MadKeithV]

Well, if you follow the the "logic" of original complaint: No matter how far back you get, there's a 3 at the same place in all three numbers, and that adds to 9. That 9 isn't going to get a 1 added to it and start a domino effect to magically make it change. :-)

That's an interesting and appealing point, but intuitively it seems to me like looking at the problem from the wrong direction (left to right rather than right to left). Don't know what to make of it, though.

Which is *exactly the same as the original complaint about 0.999... not being 1*. That's the grandparent's point. One cannot complain about the equality of 0.999... to 1, and at the same time claim that 3*0.3333... is obviously 1.

Re:I'll be first to say WTF

[MadKeithV]

I'd go one further, and say that even if a slashdotter managed to have sex with Natalie Portman, she would still not be satisfied. Hence P != NP.

Re:I'll be first to say WTF

[Captain Segfault]

Integer factorization is not (yet) np-complete, so technically no one can do what you are asking

You've got it backwards. A problem being NP-complete means you can reduce any problem in NP to it.

The problem "does N have a nontrivial factor smaller than m?" is in NP. A solver for that can easily be used to factor integers.

even if they have a legitimate proof of p=np.

Technically speaking, a legitimate proof that P=NP implies that every problem in P is NP complete.

What we're talking about is not proofs but rather unproven algorithms which seem to scale because they aren't run on hard inputs.

Re:I'll be first to say WTF

[Anonymous Coward]

. First, there are many asymmetrical encryption algorithm that are not based on factorization

More to the point, it is not even known if factorisation is part of NP at all. It could still be in P.

Re:I'll be first to say WTF

[bryonak]

The other posters have already done a good job of explaining. I'll add a graphical help.

Grab a sheet of paper and draw a horizontal line, on which you mark 0 at the left end and 2 at the right end.
Now mark 1 in the middle with a dash. Then mark 0.5. Is it the same as 1? No, there's quite a bit of space in between.
Now mark 0.666... (two thirds). It's an infinite decimal number, but it's clearly not at the same place as 1 because there is obviously some space between.
Finally, mark 0.999....
As you have hopefullly understood by now, there is nothing between 0.999... and 1. Hence on your paper, these two are for all intents and purposes represented by the same dash.

0.999...(1000 times)...9 would not be the same as 1, but slightly to the left. Thus it's not 1.
0.999...(infinite times)...998 doesn't make sense. Theoretically it would be smaller than 0.999..., but how do you add some arbitrary number the end of an infinite 0.999... sequence?

Once you have a firm enough grasp of this, you may want to try learning the epsilon-delta formalisation. Fun stuff for a certain type of mind.

Re:I'll be first to say WTF

[Chapter80]

So, let me get this straight.

In base 3, 0.0222222... == 0.1
In base 10, 0.0999999... == 0.1

so

In base 3, 0.222... == 1 and
in base 10, 0.999... == 1

and since 1 in base 3 == 1 in base 10
then obviously 2 in base 3 == 9 in base 10.

[/more_silliness]

Re:I'll be first to say WTF

[Anonymous Coward]

If there is nothing between 0.999... and 1, then you would not the logical conclusion be that there is nothing between 0.888... and 0.999..., therefore 0.888... = 0.999..., and since 0.999...... = 1 then 0.888 = 1 as well?

Just thought I'd point out that there are actually plenty of numbers between 0.888... and 0.999...
For example 0.91 and 0.98 are both clearly in between the two.

Re:I'll be first to say WTF

[doshell]

In ALL cases where f(x) exists, the limit of n as n approaches x is ALWAYS f(x). It is the same thing.

To be pedantic, that is only true if f(x) is continuous. But of course, in the situation at hand it is.

Re:I'll be first to say WTF

[doshell]

I think your problem is that you have trouble seeing the difference between a number (the abstract concept) and a representation of a number (a concrete matter of notation). You are assuming that two different representations (namely, "0.999..." and "1") necessarily correspond to two distinct numbers. However, that is not the case in the base-10 positional system for representing real numbers.

Re:I'll be first to say WTF

[caerwyn]

Err, that's not actually correct. 0.999... != .A, as you could transform any of those 9s (after the first) into an A to have a number between .999... and .A. This is like trying to say that 0.444... = 0.5, which is clearly wrong.

Also, the original comment mentioned "branches of mathematics", which is what I was curious. Hexadecimal is just a different base.

Re:I'll be first to say WTF

[Surt]

Proving P=NP by (for example) finding a polynomial time solution to a #P-complete problem won't immediately kill RSA because it's unclear (to me at least) how that would map to an efficient factoring algorithm. But a constructive proof such as what Romanov claims, i.e. an efficient 3-SAT solver, immediately deals a death blow to RSA, AES and everything else but one-time pads. That's because all these systems are polynomial time reducible to some 3-SAT instance.

As far as I know, there's no proof of that. If there was, they would be in the class np-complete rather than np-hard.

Re:I'll be first to say WTF

[Surt]

Integer factorization is not (yet) np-complete, so technically no one can do what you are asking

You've got it backwards. A problem being NP-complete means you can reduce any problem in NP to it.

The problem "does N have a nontrivial factor smaller than m?" is in NP. A solver for that can easily be used to factor integers.

even if they have a legitimate proof of p=np.

Technically speaking, a legitimate proof that P=NP implies that every problem in P is NP complete.

What we're talking about is not proofs but rather unproven algorithms which seem to scale because they aren't run on hard inputs.

I had it exactly right. They cannot use a 3-sat solver on "does N have a nontrivial factor smaller than m?" because the latter is not in np-complete. A solver for the latter can indeed be used to trivially factor integers, but since it isn't what they have they can't. Nor can anyone with an np-complete solver trivially do that.

And yes, of course a legitimate proof implies that every problem in P is NP complete. That's obvious. But it doesn't screw RSA because RSA security is based on the fact that an efficient algorithm for factoring integers is unknown, not that such doesn't exist, and everyone knows that.

Re:I'll be first to say WTF

[Whomp-Ass]

It could also be said that .999... is 1/Infinity away from 1.

i.e. .999... + 1/inf = 1

But that's as stupid as this whole argument. .999 is as close to and may as well be for all practical intents and purposes for as much as it matters to anyone equal to 1.

(.999 is still not Unity)

Re:I'll be first to say WTF

[koreaman]

Notation: The notation k.a_0a_1a_2...a_n... , where k is an integer and each a_j is an integer with 0 = a_j = 9, is defined as k + \sum_{j=1}^\infty a_j/(10^j). This geometric series clearly converges.

By this notation, 0.999... = 0 + \sum_{j=1}^\infty 9/(10^j). You may easily verify by the formula for the sum of a geometric series that this equals 1.

Is this derivation enough for you?

Re:I'll be first to say WTF

[koreaman]

Math is whatever we define it to be. You are perfectly free to define an axiomatic system in which concepts like "infinitesimals" make sense, and there are many mathematicians who have done this. I could define a formal system in which 7 = 4 if I wanted. For example, Z / 3Z (that is, the set of integers under mod-3 arithmetic)

Re:I'll be first to say WTF

[phlinn]

Actually, both numbers are both rational and real. .333=333/1000. Pi, on the other hand, is real but not rational.

The confusion isn't between two different types of numbers, it's between two different methods of expressing numbers, and confusing the representation for the number.

Re:I'll be first to say WTF

[JimFive]

What other option is there? It's either polynomial (P) or not polynomial (NP), isn't it?

NP doesn't mean Not polynomial. It means NonDeterministic Polynomial. That is, solvable in Polynomial time by a Nondeterministic Finite Automata. As opposed to P which is solvable in Polynomial time by a Deterministic Finite Automata.

Polynomial time means that as the number of inputs (n) increase the time the algorithm takes to solve the problem increases by some constant exponent (e.g. n^2 or n^3). There is also Exponential time which means the algorithmic time increases by e.g. 2^n. In between Polynomial (n^2) and Exponential (2^n) there is 2^(log n)
--
JimFive

Re:I'll be first to say WTF

[JesseMcDonald]

Obviously you and I know that 0.999... is not an approximation, but the people you would show this proof to aren't so sure. Most of the time the point you're really trying to get across is that 0.999... isn't just an approximation, and for that argument this proof, while perfectly true, is no help at all.

In order to understand that 0.999... is not an approximation you pretty much have to understand limits, and anyone who understands limits is not going to have a problem with 0.999... = 1.

Re:I'll be first to say WTF

[Captain Segfault]

I had it exactly right. They cannot use a 3-sat solver on "does N have a nontrivial factor smaller than m?" because the latter is not in np-complete.

You can use a 3-sat solver on any problem in NP. It doesn't have to be NP complete.

An instance of "does N have a nontrivial factor smaller than m?" *trivially* turns into a circuit. The circuit is just a bunch of multipliers and an OR gate!

Next up, a circuit trivially turns into a boolean formula. I hope I don't need to spell out the equivalence.

Third, they take the resulting formula and plug it into the reduction from SAT to 3-SAT.

Fourth they plug said formula into their solver.

Nor can anyone with an np-complete solver trivially do that.

Take above steps, but replace reductions depending on exactly which problem the solver solves.

And yes, of course a legitimate proof implies that every problem in P is NP complete. That's obvious.

That's great. The fact you can use a solver for any problem in NP-complete to solve any problem in NP is even more obvious. It's why NP collapses to P if NP-complete is in P!

But it doesn't screw RSA because RSA security is based on the fact that an efficient algorithm for factoring integers is unknown, not that such doesn't exist

Security by obscurity, eh? Luckily, it's not a problem for a constructive proof that P=NP, since the reductions are all known.

Re:I'll be first to say WTF

[Anonymous Coward]

Common sense is commonly wrong.

Your deep philosophical problem is something you're just going to have to get over.

Here's a hint: You don't understand infinity.

The ellipsis after the 3rd 3 represents an infinitely repeating sequence of 3s. Please consider that for a moment. An *infinite* sequence. Not a sequence that stops at some extremely small number that you can append a different value to, but an *INFINITE* sequence.

The only thing you can add to 0.999... to turn it in to 1 is 0. Or nothing, since it already IS 1. There is no difference between them other than the visual representation.

And it's spelled "integer".

Re:I'll be first to say WTF

[Cinder6]

True. I suppose there are those who think that infinity is ultimately a number, so infinity - 1 makes sense to them.

Re:I'll be first to say WTF

[Surt]

I don't know, you seem to think factorization is in np-complete while rsa think it is in np-hard. I'm going to go with rsa.

Re:I'll be first to say WTF

[TheOtherShoe]

I think this is the best explanation of NP that I have seen. Thank you!

Re:I'll be first to say WTF

[Have Brain Will Rent]

Ummmm geez I have a problem with the idea that 1/3 = 0.333... because it isn't true.

Re:I'll be first to say WTF

[Have Brain Will Rent]

Hmmm, I think that if you are going to start asserting things like that then you need to be making some unspoken assumptions explicit. For one thing all the arguments I've seen so far (and of course I may have skimmed too quickly) are implying that the limit of F(x) is asymptotically approaching a single value and that's certainly not necessarily true.

Re:I'll be first to say WTF

[kylemonger]

Proving P=NP by (for example) finding a polynomial time solution to a #P-complete problem won't immediately kill RSA because it's unclear (to me at least) how that would map to an efficient factoring algorithm. But a constructive proof such as what Romanov claims, i.e. an efficient 3-SAT solver, immediately deals a death blow to RSA, AES and everything else but one-time pads. That's because all these systems are polynomial time reducible to some 3-SAT instance.

As far as I know, there's no proof of that. If there was, they would be in the class np-complete rather than np-hard.

It was proven when the first NP-complete problem was shown to be complete for the NP complexity class. An efficient solution to an NP-complete problem is an efficient solution to all NP problems, not just NP-complete ones. You don't have to prove that an NP problem is NP-complete for that solution to apply, you only have to show that a problem is in NP, i.e. that a "yes" answer to the decision version of the problem can be verified in polynomial time. For an encryption problem the decision version is "does the output of this encryption function with ciphertext C and key X produce output that looks like a properly decrypted message?" Once you have that verification method, it can be encoded as a 3-SAT instance that can only be satisfied if the verifier would be satisfied. Since you have an efficient 3-SAT solver (assuming Romanov has the goods), when you feed the verifier 3-SAT instance into it, you are effectively exploring the exponentially large key space in polynomial time.

That's the power of NP-completeness--- just having a polynomial time verifier is all you need to be able to produce a polynomial time solver. It doesn't matter what the computational problem is, if you can verify the solution in polynomial time, you can solve the problem in polynomial time if you have a polynomial time solver for any NP-complete problem.

Re:I'll be first to say WTF

[Have Brain Will Rent]

Infinity represents a value which, it seems to me, makes it a number... just not a number with a fixed value. You can do calculations with Infinity/Infinities which, again I think, qualifies it as a number... If 1 is a number and you assert 0.99999.... equals 1 you are claiming that the sum of 9/(10**N) [as N ranges from 1 to X] is 1 where in this case X is assigned the value of Infinity. IF you can assign it to a variable then it is a number. To restrict the definition of "number" to being "constant" or even "enumerable" is too restrictive... Is Aleph-Null not a transfinite *number*? But wth it's Friday night, I'm tired enough that I may as well be drunk and I haven't thought of this particular stuff for a painfully long number of years so I'm probably wrong.

No! No! No!

[Anonymous Coward]

You're clearly a communist trying to pollute our Precious Bodily Fluids. (I'm intrigued that that actually spell checks. A "sanity check" would fare much worse. Oh, well.)

Re:I'll be first to say WTF

[fishexe]

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

Because this site's tagline is "NEWS FOR NERDS." (capitalization in original)

Re:I'll be first to say WTF

[JesseMcDonald]

Could you be more specific? E.g., which assertions, and which unspoken assumptions?

For one thing all the arguments I've seen so far ... are implying that the limit of F(x) is asymptotically approaching a single value and that's certainly not necessarily true.

Certainly not. For one thing, the limit of a function of one variable with respect to that variable doesn't approach anything; it's either undefined or a specific value. The function itself may approach a value (e.g. F(x) approaches one as x approaches +infinity) but the limit, if it exists, is a constant (e.g. \lim_{x\to\infty}F(x) = 1).

Re:I'll be first to say WTF

[Anonymous Coward]

0.99999.... has to be 1 because the real numbers are Hausdorff: any two different numbers have to have open sets around them that don't intersect. Alternatively, if two points are in every neighborhood of each other, they are the same (this is not true of people, for example :). Alternatively, any two numbers at a distance of 0 from each other have to be the same. What's the distance from 0.99999.... to 1?

If you don't impose the Hausdorff condition on Cauchy sequences of rational numbers, 0.99999999 isn't equal to 1. There will be, instead, an infinite number of different sequences of rational numbers for each real number, and mathematicians will need to talk explicitly about the class of sequences that are really at the same point in the line.

If you restrict to decimal sequences, only terminating decimals will have two different representations, which doesn't seem as bad, but it still will force people to talk about classes of decimal sequences that reference the same point in the line. ...these classes of decimal sequences are called real numbers.

Re:I'll be first to say WTF

[fishexe]

I think the hole in your logic may be that 0.333... == 1/3. I think 0.333... may only be a very close numerical approximation of 1/3, but 1/3 cannot be expressed absolutely as a number (even assuming infinite 3s).

No, it is not an approximation. It is exactly 1/3. If that were not true, all of mathematics would break. Think about it: If 1/3 were not exactly .3333... (infinite) then you would have to add (or subtract, but it seems like your implication is that 0.333... = 0.333...343... (with infinite 3s and a 4 in place n). If that were the case, you could divide 1 by 3, render it as a decimal, multiply it by 3, and get a number greater than 1. Repeat ad nauseum to prove 1=7, 1=2,467,946, et cetera. If 1/3 is defined as exactly equaling .333... (infinite) and 1 is defined as 0.999... (infinite) then mathematics is consistent, performing a function on its inverse always gives back the original number, and life can go on.

I have read about the issue of 0.999... = 1 several times, but the explanation is much more complex than this.

Only because some folks don't like the simple explanation. The complex explanation is only necessary to put all the nonsense to rest.

Re:I'll be first to say WTF

[Have Brain Will Rent]

I misspoke (mis-typed?) there, I had actually been picturing the limit of the derivative of F(x) as x approached some value where F(x) was discontinuous... hmmm, now I'm not sure where I had been going with that.... I plead Friday nightism!

Re:I'll be first to say WTF

[fishexe]

(reposting because slashcode butchered the middle of my post)

I think the hole in your logic may be that 0.333... == 1/3. I think 0.333... may only be a very close numerical approximation of 1/3, but 1/3 cannot be expressed absolutely as a number (even assuming infinite 3s).

No, it is not an approximation. It is exactly 1/3. If that were not true, all of mathematics would break. Think about it: If 1/3 were not exactly .3333... (infinite) then you would have to add (or subtract, but it seems like your implication is that 0.333... (infinite) < 1/3 so we'll go with that) something to 0.333... (infinite) to get 1/3. This would have to have a non-zero digit somewhere, so let's call it 0.000...X0... with digit X in the nth place and infinite 0s thereafter, so that 0.333... + 0.000...X00... = 1/3. Since X is at least 1, this means 1/3 > = 0.333...343... (with a 4 in place n and infinite 3s thereafter). If that were the case, you could divide 1 by 3, render it as a decimal, multiply it by 3, and get a number greater than 1. Repeat ad nauseum to prove 1=7, 1=2,467,946, et cetera. If 1/3 is defined as exactly equaling .333... (infinite) and 1 is defined as 0.999... (infinite) then mathematics is consistent, performing a function on its inverse always gives back the original number, and life can go on.

I have read about the issue of 0.999... = 1 several times, but the explanation is much more complex than this.

Only because some folks don't like the simple explanation. The complex explanation is only necessary to put all the nonsense to rest.

Re:I'll be first to say WTF

[fishexe]

Please ignore parent post, I foolishly left a < in one formula and a > in a later formula so that slashdot thought everything in the middle was an html tag, and omitted it. Please read the repost (also attached to GP) instead.

Re:I'll be first to say WTF

[Tacvek]

Indeed, all P problem (or NP problems for that matter) are PSPACE.

Re:I'll be first to say WTF

[fishexe]

You didn't learn about convergence in whatever passes for precalculus mathematics in your country.

Probably in the US. That's where I took precalculus and I didn't learn it at that stage. And then people wonder why our high school grads test badly at math. Anyhow, my cohort didn't learn about convergence (formally) until 2nd-semester calc in college (though the more competent among us had already learned it on our own).

Re:I'll be first to say WTF

[fishexe]

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 like your analogy, but I would amend it to: "if you can't determine either yes or no, then it continues to be a mystery attracting all sorts of speculation from the trip-planning (and/or mathematical) community."

Re:I'll be first to say WTF

[fishexe]

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

Would he have to become a salesman as well?

Re:I'll be first to say WTF

[fishexe]

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.

Where does NP-hard enter into all this?

Re:I'll be first to say WTF

[fishexe]

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.

Does this mean Romanov has successfully slept with Natalie Portman, or that he's just given us instructions on how to sleep with her, and left it up to us to test his method?

Re:I'll be first to say WTF

[EllisDees]

>I can usefully define 0.999... as the largest number which is less than 1 and reason about it on that basis.

I believe those are called infinitesimals, but they are not a feature of 'standard' mathematics.

(hey! paste works now!)

Re:I'll be first to say WTF

[doshell]

I'll take a stab at this. To begin with, one thing most people have been missing (or at least not stating explicitly) in this thread is the following fact: mathematical notation is a matter of convention. That is, the meaning of notation is not god-given, nor is it a matter of intuition; it derives from precise and agreed upon rules.

Here we are talking about representing real numbers in decimal notation. So what are the agreed upon rules for this notation? Let's consider two cases: first the case of a finite representation, and then the case of an infinite representation.

For a finite representation, the rule is the following: if the representation is in the form "0.abcd", the corresponding number is given by the formula:

0.1*a + 0.01*b + 0.001*c + 0.0001*d.

Of course, the rule above only works for representations between zero and one with only four decimal digits; but I'm sure you can figure out what to do with longer representations. (I do not want to post the general formula here so we do not get unnecessarily distracted by heavy notation.)

Now consider an infinite representation. Can we apply the same rule as for the case of a finite one? Well, we have a problem: since there is an infinite number of digits, we are not able to carry out the sum given by the formula above and arrive at a result in a finite amount of time. In other words, we have a "sum of an infinite number of terms", which mathematicians call a series.

It happens that there is a whole theory of series, and that theory allows us to calculate the sum of a series without actually performing an infinite number of additions. The sum may be finite or infinite (it may be surprising to you that the sum of an infinite number of non-zero terms can be a finite number, but I will ask you to accept this as fact; I would explain it to you, but that's tangential to this discussion).

So, when we have an infinite representation of the form "0.abcde..." (the digits go on), we may imagine it to be the result of the "sum"

0.1*a + 0.01*b + 0.001*c + 0.0001*d + 0.00001*e + ...

but in fact the corresponding number is obtained by considering the series made up of the terms in the sum, and determining the sum of the series.

So, when we have the infinite representation "0.999...", the corresponding number is given by a series whose first few terms are

0.9, 0.09, 0.009, 0.0009, ...

and it turns out (according to the theory of series) that the sum of this particular series is 1.

Of course, the interesting and tricky part is knowing how to determine the sum of a series; but that really is not my point here. My point is that the fact that 0.999... = 1 rests on agreed upon rules on which number corresponds to a given decimal representation, and those rules assign the same number to "0.999" as they do to "1". Maybe this is not the answer you were expecting, because you would like an intuitive explanation that would make you feel it makes sense, instead of having to accept it as being simply the result of the application of seemingly arbitrary "agreed upon rules". Other people in this thread have tried, to some degree of success, to provide such intuitive explanations, and I welcome them. I'm merely making the point that, even though intuition plays an important role in mathematics, the meanings we ascribe to mathematical symbols are a matter of convention, not intuition.

Re:I'll be first to say WTF

[Garridan]

You don't know your math history. Wiles' proof of FLT took about a year to verify and repair. It took a number of years before a plausibly verifiable proof of the four color theorem was published. Perelman's dozen-page proof of the Poincare conjecture was so lacking in details that it was fleshed out to over 300 pages. History shows that proofs of hard theorems are not easy to verify, and definitely not "very easy". Even if the proof is constructive and is provably guaranteed to run in (say) cubic time, it needn't be so simple as a triple-nested for-loop. It could quite likely bear many similarities to exponential algorithms, but exploit a subtle property that just so happens to be bounded by a polynomial in the size of the input.

Re:I'll be first to say WTF

[Anonymous Coward]

If .999... isn't equal to 1, then by how much do the two numbers vary? The answer is .0...1. That's inconceivable-- impossible to imagine a number that goes on to infinity, *stops* and then adds a 1.

Secondly: .999... = x .999... * 10 = 9.999.... | 10 * x = 10x

9.999 - .999 = 9.0 exactly | 10x - x = 9x

9.0 / 9x = 1

x = 1, .999...

Re:I'll be first to say WTF

[SanityInAnarchy]

I think your examination of my example of poetry and hairstyling engineers is quite arbitrary.

More arbitrary than your insistence that engineering concern itself with physical things only?

Even the work of a poet can withstand a large electro-magnetic pulse, either in our memory or in a printed piece of dead tree,

Ever hear of the PGP book?

Software Engineers ARE Software Developers with a cooler name.

Yet they are taught different things, at least in the place I've seen.

...a true moving target of a curriculum if ever there was one.

I wouldn't have it any other way.

Re:I'll be first to say WTF

[Captain Segfault]

I don't know, you seem to think factorization is in np-complete while rsa think it is in np-hard. I'm going to go with rsa.

I think no such thing, and neither do they.

Remember how my first response in this thread was that you had your definitions backwards? I'm saying factoring is NP-easy. Nobody who actually knows what they're talking about thinks its NP-hard.

A problem doesn't need to be hard to reduce it to SAT.

Re:I'll be first to say WTF

[Anonymous Coward]

Are you sure about that? I thought the idea was to translate instances of the more difficult problems into instances of the easier problems (and then to use the solution you already have for the easier problems).

Also, a solution is by definition generic--otherwise it wouldn't be much of a solution.

No, because some of the easy problems have easy solutions that can't be generalized, e.g.

1. Given a set of N numbers, find a subset whose total is as high as possible. (Easy solution: pick all the positive numbers and none of the negative ones.)
2. Given a set of N numbers, find a subset whose total is exactly zero. (This is the subset sum problem, and is NP-complete; any P-level solution to a NP problem could be generalized to all problems in NP, though obviously that would be overkill for many of them.)

And, it doesn't really matter how much time it takes to 'translate a solution' because if it truly is a solution, you should only have to do it once.

The point was that translating a solution isn't the problem (because that part is O(P(N)) where P(N) is some polynomial of N); the problem is coming up with a O(P(N)) solution to any NP-complete problem in the first place.

Re:I'll be first to say WTF

[emurphy42]

The above post was me, btw, I didn't realize it'd lost track of my login.

Re:I'll be first to say WTF

[Have Brain Will Rent]

0.333... = 0.999...

Must be that New Maths ah bin heering 'bout so much!

Re:I'll be first to say WTF

[dynamo]

Although I am pretty convinced by the previous answer here, there's been so much discussion on it and whether 3x0.333... is equal to 1 or 0.999... that I felt compelled to offer this one:

A = 0.999...
B = 1.0

This simplifes the question to whether A = B. Now:

C = 10 * A = 10 * 0.999... = 9.999...
D = C - A = 9.999... - 0.999... = 9.0

At this point, we've worked out that C is equal to the sum of 10 A's, and then we've turned around and subtracted out one of those A's, calling this D. Logically this means that D would be left with 9 A's. To find out whether 9 A's are equal to 9 B's, we can divide by B and if the answer is 9 exactly, that is math's way of telling you that B == A.

D / B = 9.0 / 1.0 = 9.0.

Check and mate.

Re:I'll be first to say WTF

[Captain Segfault]

A problem doesn't need to be hard to reduce it to SAT.

And also note that you don't need to be able to reduce SAT to a problem for it to be hard!

Factoring is almost certainly easier than SAT but harder than anything in P.

Re:I'll be first to say WTF

[Barrie_rdv]

So how would you verify that an optimal solution to the travelling salesman problem is in fact optimal in polynomial time?

Re:I'll be first to say WTF

[kylemonger]

So how would you verify that an optimal solution to the travelling salesman problem is in fact optimal in polynomial time?

That question can't be posed as an NP decision problem, so it is out of domain.

The NP traveling salesman decision problem:

Given a graph G and distance D, is there a path that traverses all the nodes that is shorter than D?

The co-NP traveling salesman decision problem:

Given a graph G and distance D, are all paths that traverse all the nodes at least as long as D?

The NP question has a verifier certificate for the "yes" answer but not the "no" answer. The co-NP question has a verifier certificate for the "no" answer, but not the "yes" answer. To provide an efficient and easily verifiable answer to your optimization question a co-NP-complete solver is needed.

Re:I'll be first to say WTF

[TechyImmigrant]

Yes. You are quite right. I was aiming more for the humorous end of things.