Polynomial Time Code For 3-SAT Released, P==NP 700
An anonymous reader writes "Vladimir Romanov has released what he claims is a polynomial-time algorithm for solving 3-SAT. Because 3-SAT is NP-complete, this would imply that P==NP. While there's still good reason to be skeptical that this is, in fact, true, he's made source code available and appears decidedly more serious than most of the people attempting to prove that P==NP or P!=NP. Even though this is probably wrong, just based on the sheer number of prior failures, it seems more likely to lead to new discoveries than most. Note that there are already algorithms to solve 3-SAT, including one that runs in time (4/3)^n and succeeds with high probability. Incidentally, this wouldn't necessarily imply that encryption is worthless: it may still be too slow to be practical."
Probably Wrong but Clearly Falsifiable (Score:5, Interesting)
Even though this is probably wrong, just based on the sheer number of prior failures ...
Okay, so I'm going to agree with you that it's probably wrong. After reading the paper once last night in a sort of sleepy state, it's certainly a novel way of massaging each 3-Sat problem into an expanded space of memory (compact triplets structures) and then reducing this to solve the problem (all within polynomial time).
So the great thing about this paper is that it's short, it's not theoretical (which is a double-edged sword)/has been implemented (in Java, no less) and it's incredibly falsifiable. I'm not intelligent enough to poke holes in his proofs for this work but people can apply the code to DIMACS formatted [pdmi.ras.ru] problems to their heart's content and if they find one that produces the wrong answer then this is falsified.
I hope we find someone capable of commenting on the proof involving the transformation of the problem from compact triplets formula to compact triplets structure and the hyperstructures presented in the paper. If this is legit, the 3-Sat problem is one that more complex problems are reduced to in order to show that said complex problems are NP-complete. And that's something that's been proved by the Cook-Levin theorem [wikipedia.org] and given in the classic Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson.
Refreshingly tangible implementation, if I may say so myself!
Re:Probably Wrong but Clearly Falsifiable (Score:5, Interesting)
Maybe I'm overlooking something, but to me it looks like they're doing the reduction to a polynomial-time problem already at the very beginning of the paper (I guess if there is a fault, there it hides). As soon as they go to "compact triplet" structure, the instance of 3-SAT is polynomial-time solvable using a trellis algorithm. Yes, very similar to the algorithm that is employed to decode convolutional codes.
In fact they're decomposing the initial 3-SAT problem into multiple "compact triplet" 3-SAT problems intersected using an AND operation. But as these intersected 3-SAT formulas use the same variables, without any interleaving (permutation) applied, the trellis algorithm still applies (just like solving for a convolutional encoder with > 1 check bits per bit).
Thinking once more about that: the compact triplet structure is clearly not general enough to express generic 3-SAT problems. This is like attempting to transform a quadratic optimization problem x^T*H*x involving a symmetric matrix H into a corresponding problem with a tri-diagonal matrix H.
The only way I see they could do the transform is by introducing exponentially many helper variables, thus moving the problem back into NP again. But it does not look like they're attempting something like that.
Re:Probably Wrong but Clearly Falsifiable (Score:5, Informative)
What, exactly, is 3-SAT? (Score:4, Insightful)
Re: (Score:3)
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? (Score:5, Informative)
It is indeed quite simple. Imagine a long string of operators like this (! is "not"):
(x1 or x4 or !x3) and (x1 and !x4 and x3) and (x2 or !x1 or !x4) etc.
The question is "Is there a way to assign true/false to all the variables such that the end result is true".
This is a satisfiability problem (SAT), and what makes it 3-SAT is that it has three variables per clause.
Re:What, exactly, is 3-SAT? (Score:5, Informative)
The clauses in 3sat are required to be disjunctions (OR).
Re: (Score:2, Informative)
Did you check the simple wiki?
http://simple.wikipedia.org/wiki/Boolean_satisfiability_problem [wikipedia.org]
Re: (Score:3, Informative)
I tried to look the problem up on Wikipedia, and all I got was inscrutable high-level math. From what I can gather, I seems like something that could be explained in layman's terms. Would someone be kind enough to do so?
3-sat: a series of 3-term clauses, of the form: _clause1_ AND _clause2_ AND ... _clauseN_. Each clause[i] consists of (term1 OR term2 OR term3). Each term may be negated. The same term may appear in multiple clauses. The problem: find all solutions where this evaluates to true, if any. (Find the solution space.) An exhaustive search of the term space is NP-complete (this ought to be obvious).
Not a complicated problem to understand, at all. And a fairly useful one to solve. Since boolean logic isn't
Re: (Score:2)
Re:What, exactly, is 3-SAT? (Score:4, Insightful)
A small correction. The NP-Complete problem is "Is there any input for what it evaluates to true?". NP problems are exclusively yes/no ones.
Now, if you solve the SAT problem, you can derive an algorithm for calculating the solution space. It will probably take exponential time. You can also derive an algorithm for finding an input that evaluates to true in polynomial time.
Re:What, exactly, is 3-SAT? (Score:5, Informative)
Sir –
I did some graduate research on satisfiability [wikipedia.org], so perhaps I can offer some illumination.
Satisfiability is a logic problem. Given a set of clauses that "or" a set of literals, which literals (and clauses) may be true or false, all "and"ed together, the question is: is there a set of literals (when true or false) that result in the overall statement being true. E.g.
X = (A or B) & (!A or !B) & (A or !B)
The question is: Is there a combination of A and B being true or false that would result in X being true? (In this example, X is true when A is true and B is false.)
3-SAT is satisfiability but with only 3-literals per clause e.g.
X = (A or B or C) and (A or !B or !C) and (!A or B or C) ...
There's a polynomial-time mapping from any satisfiability problem to 3-SAT, as there is between all NP complete [wikipedia.org] problems, which mapping is why they are so-classified. In other words, if you solve one NP complete problem in polynomial time (namely big-O notation O(ax^n) where n is the complexity i.e. number of literals) you solve them all in polynomial time. The most famous of these NP complete problems is probably the Knapsack problem [wikipedia.org], though there are quite a few [wikipedia.org].
All to say, it's a logic puzzle that has quite a few applications but no simple solution yet.
I'm not sure if the above is in layman terms, but I hope it is somewhat helpful.
Re:What, exactly, is 3-SAT? (Score:5, Informative)
Correction: the big-Oh should be O(m*n^c), where c is a number that does not increase with the complexity of the input, though `n` and 'm' may.
Usually the size of the input increases complexity, but I believe in the case of satisfiability that complexity is proportional to the number of Horne clauses - clauses with at most one positive literal - because of difficulties reducing Horne clauses. I seem to recall that reducing Horne clauses to non-Horne clauses is itself a NP complete problem, everything else (which is severable) in determining satisfiability is provably polynomial.
In Vlad's proof he's found a solution to NP problems that are O(m * n^4).
Re: (Score:3)
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: (Score:2)
Re: (Score:3)
Or something like that if I remember correctly.
Re: (Score:2)
Re:What, exactly, is 3-SAT? (Score:5, Funny)
Re:What, exactly, is 3-SAT? (Score:5, Informative)
Linguam romanae scio. Latina difficila non est; ego in annis tribus didici.
Uh... I know the Roman language. Latin is not difficult; I learned it in three years.
?
Re:What, exactly, is 3-SAT? (Score:4, Funny)
"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? (Score:5, Funny)
If you're so good at it, at least translate the line for us!
smartass...
Re:What, exactly, is 3-SAT? (Score:4, Funny)
encryption (Score:5, Informative)
Incidentally, this wouldn't necessarily imply that encryption is worthless: it may still be too slow to be practical.
No, it means good encryption will be much less practical. Computers will always get faster so "too slow" is not a good argument. If P != NP you can always make encryption too hard to break by increasing the key size - the cost to encrypt and decrypt only goes up polynomial with key size but cost to break it goes up exponentially, which makes it too hard even for those with supercomputers. If P = NP it means the cost to break it only goes up polynomially. This put the cost to encrypt in the same realm as the cost to break. So you can use much bigger keys but it becomes more expensive and may stop petty criminals but won't stop people with supercomputers.
Re: (Score:3)
Re: (Score:2)
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 (Score:4, Interesting)
You really don't know what are you talking about, don't you? Here is a counter example: assume the encryption/decryption is O(n^2), assume the cryptanalysis is O(n^3), that is, polynomial. You can choose n so that the cryptanalysis is arbitrarily more difficult than the encryption, so this result alone (if it's true) doesn't mean a thing for crypto.
Re:encryption (Score:4, Informative)
Re: (Score:3)
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.
Goldbach Conjecture (Score:5, Funny)
I have code for a solution to the Goldbach Conjecture, but it doesn't fit into my free storage on github....
Re: (Score:3)
Intel and AMD both hope P!=NP (Score:2)
Interesting... (Score:4, Funny)
Re:Interesting... (Score:5, Funny)
Welcome to the club. My friends and colleagues routinely think of me as "one of the smartest people they know" (or so I've been told). Articles like this remind me of my true status, which is helpful in not getting cocky.
Romanov's "algorithm" (Score:4, Interesting)
Romanov's algorithm strongly resembles an algorithm from a debunked paper published around 2004.
Sergey Gubin wrote a series of similarly designed proofs [arxiv.org] around 2004. Instead of Romanov's notion of "concretization," Gubin used the term "depletion." Gubin's paper was debunked [arxiv.org] 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: (Score:3)
Re:I'll be first to say WTF (Score:5, Insightful)
Not to get completely off the subject, but there are many perfectly understandable proofs of why 0.999... = 1. For instance, one of the things that defines what a real number is that it is not exactly the same as a different number. Seems pretty common sense, huh? So what number, exactly, comes between 0.999... and 1? Like you said, those 9s go on forever, so if there is nothing that you can add to the first term to turn it into the second, they must be the same. They are just 2 different ways of expressing the exact same number. You probably don't have a problem with the idea that 1/3 = .333..., so multiply both sides by 3 and what do you get?
There's even a wikipedia page that I'd totally paste in here if Chrome was able to do so.
Re: (Score:3)
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: (Score:3, Insightful)
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: (Score:3)
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: (Score:3)
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 (Score:4, Informative)
Let me try to address your questions in a manner that is not disrespectful.
1) The assertion that 0.999... = 1 is not equivalent to or in any way related to assertions like 0.888... = 1, which are false (why? there exists a real number between 0.888... and 1, take 0.9 for example). However, you could think of it as being related to the assertion that 0.888... = 8/9.
2) Yes, the assertion has everything to do with the infinite number of repeating digits. For comparison, the assertion that 0.999...9 = 1, where there is a finite number of 9s, is false, no matter how large that number of 9s is.
3) There are many explanations behind this infinite nature. One of the basic ones is that 0.999... is actually representing a series (infinite sum), in this case a geometric series of the form 0.9 * (0.1^0 + 0.1^1 + 0.1^2 + 0.1^3 + ...). The sum of a geometric series with ratio r is 1/(1-r), and so the sum of the series is 0.9 * 1/(1-0.1) = 0.9 * 1/0.9 = 1. I've seen some other, more elegant explanations offered here and elsewhere, but this explanation is sound and requires only knowledge of calculus (the proof of the summation formula requires limits).
4) There is no "property" that enables this assertion. Instead, this claim arises because of the disparity between the representation of numbers and the numbers themselves. Within the real numbers, 0.999... and 1 are not distinct. They appear distinct because of the decimal representation (and indeed, a representation in any base exhibits the same characteristic). This is true for all rational numbers when represented as decimals, e.g. 0.4999... = 0.5 or 0.888... = 8/9 from above.
Re:I'll be first to say WTF (Score:5, Informative)
One of the first things I learned is that 0.333... (as an example) is an approximation of 1/3. A fraction such as 1/3 cannot be 100% accurately represented in a decimal system.
This is incorrect, and is apparently the source of most of your confusion. 1/3 = 0.333...; there's no approximation going on. 1/3 is approximated by 0.3, and 0.33, and 0.333, but the infinite decimal is *not* an approximation.
The problem here is that people are generally very ill-equipped to handle the idea of infinity, and a lot of common sense doesn't really work. You can't "tack another 5 on the end" of 0.999... to get a number halfway between 0.999... and 1, as some other poster commented, precisely because there is no end for it to be tacked onto. This is why it's ultimately equal to 1.0.
Re:I'll be first to say WTF (Score:5, Informative)
there's a 9 at the end
This is why your understanding fails. There is no end.
What is really so complicated by these simple examples:
1/3 + 1/3 + 1/3 = 3/3 = 1
And since 1/3 exactly equals 0.333... we have:
0.333... + 0.333... + 0.333... = 0.999...
And since the two sums are exactly equal, 0.999... equals 1. It's not really that magic, and your normal daily life will not be affected. It is, however, true.
Re: (Score:3)
um, no. 0.333... is the decimal expansion of 1/3. It just has a clumsy decimal (base-10) expansion. The ternary (base 3) expansion is quite simple: 0.1.
Or IS it that simple:
I thought the ternary expansion of decimal 1/3 was (base 3) 0.1000....
Next you're going to tell me that (base 3) 0.1 == (base 3) 0.1000....
[/silliness]
Re:I'll be first to say WTF (Score:5, Informative)
1.) 0.99999... * 10 = 9.99999...
2.) 9.99999... - 0.99999... = 9
3.) 9 / 9 = 1
Therefore 0.99999... = 1. Q.E.D.
Re:I'll be first to say WTF (Score:4, Informative)
You made an error in your third line:
.5 * 10 = 5 .5 = 4.5 = 9 * .5
5 -
4.5 / 9 = 0.5
0.5 = 0.5. QED.
Re: (Score:3)
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: (Score:3)
Damn you math geeks. Why must you come here and spew your incomprehensible formulas.
I agree. Can we have a car analogy? Or at least Natalie Portman?
Re: (Score:2)
Damn you math geeks. Why must you come here and spew your incomprehensible formulas.
I agree. Can we have a car analogy? Or at least Natalie Portman?
Given a choice, I'd rather have Natalie Portman than a car analogy :)
Re:I'll be first to say WTF (Score:4, Informative)
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 (Score:5, Informative)
NP is short for Natalie Portman, and the car analogy follows:
Adleman's chief scientist, Nickolas Chelyapov, offered this illustration: Imagine that a fussy customer walks onto a million-car auto square and gives the dealer a complicated list of criteria for the car he wants.
"First," he says, "I want it to be either a Cadillac or a convertible or red." Second, "if it is a Cadillac, then it has to have four seats or a locking gas cap." Third, "If it is a convertible, it should not be a Cadillac or it should have two seats."
The customer rattles off a list of 24 such conditions, and the salesman has to find the one car in stock that meets all the requirements. (Adleman and his team chose a problem they knew had exactly one solution.) The salesman will have to run through the customer's entire list for each of the million cars in turn -- a hopeless task unless he can move and think at superhuman speed.
This serial method is the way a digital electronic computer solves such a problem.
Re:I'll be first to say WTF (Score:5, Informative)
You left out the most important part. It takes lots of work to find the car, but it takes a short time to check that it's the right car once it's found. In other words, if you're lucky and always guess the right car on your first try (in other words nondeterministically), you can check that it's the right solution quickly (in polynomial time). Nondeterministic polynomial time = NP.
In 3-SAT, it takes exponential of time to find the assignment to the variables that satisfies all the conditions, but it takes polynomial time to check whether a particular assignment is correct. It takes exponential time to factor a product of two large primes, but it takes polynomial time to make sure it's the correct factorization.
Re:I'll be first to say WTF (Score:4, Informative)
Actually, it's unknown whether integer factorization (into primes) is an NP problem [wikipedia.org]. 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 [wikipedia.org] 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 (Score:5, Funny)
And if each car is located in a different city, then he'll have to go travelling in order to test all the criteria. Of course, he wouldn't want to end up hitting the same city twice...
Re: (Score:3, Funny)
Re: (Score:3)
Re:I'll be first to say WTF (Score:5, Interesting)
I want to pick the lock on your car. It's one of those fancy code entry locks and I only have to press 3 buttons, but that's not really important.
Everyone has been saying that it's very, very hard (NP) to crack the code by trying combinations. Now there's a guy saying it's not quite as hard (P) and he wants everyone on the internet to check his work.
Re:I'll be first to say WTF (Score:5, Interesting)
But if this guy can "crack the code" (that is, solve the 3-SAT problem), he has proven that NP is not harder than P.
The debate about whether NP is harder than P has been going for a long time.
Re: (Score:3)
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 (Score:5, Funny)
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 (Score:5, Funny)
what does P stand for?
Portman.
Oh wait, sorry, I was answering the comment above yours...
Re: (Score:2)
Re: (Score:2)
"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 variable
Re:I'll be first to say WTF (Score:5, Insightful)
Well there probably should be at least one refuge where computer science nerds can discuss news that matters. Unlike mainstream media the news here shouldn't have to pander to the lowest common denominator - if you don't care for this article move on to one in a field that you are interested in. If you are not a nerd at all then news for nerds may not appeal to you.
Re:I'll be first to say WTF (Score:5, Funny)
Are we expected to get a CS degree before reading Slashdot?
Yes. And a PhD before posting. Didn't you read the T&Cs?
Re: (Score:3)
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 (Score:4, Insightful)
Please turn in your geek card. This is basic CS stuff.
Re:I'll be first to say WTF (Score:4, Informative)
If you understand Turing machines and big-O notation (and if you claim to be a programmer, you should) and polynomials (and if you claim to understand big-O notation, you should):
Re: (Score:3)
There is also NP-Hard. Essentially NP-complete is the intersection of NP and NP-Hard.
Simple Explanation (Score:2)
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, travellin
Re:I'll be first to say WTF (Score:4, Funny)
Make your own (Score:3)
Why not create your own incomprehensible CS paper?
http://pdos.csail.mit.edu/scigen/ [mit.edu]
Re: (Score:2)
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 (Score:5, Informative)
All the experts in the field agree that P != NP
Absolutely untrue. All experts in the field that I've spoken to think that P is probably not equal to NP, but that a proof either way is going to be very hard.
Re:I'll be first to say WTF (Score:5, Insightful)
Absolutely untrue. All experts in the field that I've spoken to think that P is probably not equal to NP, but that a proof either way is going to be very hard.
Absolutely correct. The difference between say, computer science and sociology, is that computer scientists require absolute proofs. In other words, if you claim that P==NP, as this paper does, then I require you to show that it is so for all possible inputs.
The paper, in fact, does not show such a thing. To the contrary, it fails to show a sound and complete reduction of 3-SAT to hyperstructures, or CTF or CTS or whatever other acronyms were made up by the author. I'm not saying that he's wrong, simply that this is not a proof - it is only a claim. The author claims to have "proven" his algorithm is polynomial time by giving it a smattering of inputs and noting that the time the algorithm took to complete increased by a polynomial factor of the input size.
Clearly the author has not studied his algorithmic complexity texts well enough to understand the definition of Big-O. Big-O only claims that algorithmic growth is asymptotic to a given curve as the input size goes to infinity from some value n0. In other words, many algorithms may display linear growth to a point, and then become exponential after input size greater than n0. A statistical analysis will not prove anything. The author needs to do a full algorithmic analysis instead.
I predict this paper will be rapidly debunked and we will still not know if P==NP.
Re:I'll be first to say WTF (Score:5, Interesting)
I predict the same thing; however how awesome would it be it the paper is correct!
I wouldn't use the term debunked. Shown to be incorrect is better. Which is fine and expected in science. To me ;debunked; implies some sort of fraud is taking place.
Re: (Score:3)
Re: (Score:3)
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: (Score:3, Informative)
That's exactly right!
Please read these two blog posts about the consequences of P=NP from an expert in the field:
http://rjlipton.wordpress.com/2009/09/18/why-believe-that-pnp-is-impossible/ [wordpress.com]
http://rjlipton.wordpress.com/2009/02/18/insider-baseball-and-pnp/ [wordpress.com]
Re:I'll be first to say WTF (Score:5, Informative)
And the vague reference to "encryption" in TFS is silly; there aren't any crypto algorithms in use whose security rests on P != NP.
Every symmetrical encryption algorithm in the field currently relies on the idea that the computation of the plaintext from the ciphertext and key is easily verifiable, but the computation of the key from the ciphertext is hard. Many can be analyzed if you can perform same difficult mathematics in a short time.
Every asymmetrical encryption algorithm in the field relies on the factoring problem, which is NP hard. If P==NP, then suddenly we know the factoring problem is NP easy. Further, solving one NP hard problem would effectively supply new strategies to solve other NP hard problems. QED.
Encryption relies on the theory that some shit is just hard to do. Not that we don't know how, but that from what we know it's trivially doable but takes too god damn much work that can't be done in any shorter than a huge fucking length of time even with all the resources in the world pointed at it.
Re:I'll be first to say WTF (Score:4, Interesting)
While you did a good job at explaining the general relation between NP-hardness and cryptography, there are several factual errors in your message. First, there are many asymmetrical encryption algorithm that are not based on factorization: many are based on the discrete logarithm, and other hard problems are used in a few construction. Second, we don't know whether factoring is NP-hard and it is conjectured not to be NP-hard (which does not mean we think it's polynomial!).
Also, you seem to have missed the point of NP-harder or NP-completeness: if we can sole one NP-hard problem in polynomial time, then by definition this proves that P=NP and we can solve all NP problems in polynomial time. (A problem is said to be NP-complete if it is NP-hard, and it is itself in NP)
Re: (Score:3, Interesting)
Every asymmetrical encryption algorithm in the field relies on the factoring problem, which is NP hard. If P==NP, then suddenly we know the factoring problem is NP easy. Further, solving one NP hard problem would effectively supply new strategies to solve other NP hard problems. QED.
No. You're neglecting the discrete log problem which underpins Differ Hellman. There are probably other esoteric algorithms that rest on other hard problems like the knapsack problem. And I believe you also misstated the RSA assumption.
The RSA assumption is that computing the Euler phi/totient function for n=p*q where p,q are prime is HARD*. The RSA assumption is RELATED to but NOT EQUIVALENT to factoring. The relationship is that RSA can be reduced to factoring, i.e., factor n into p,q and return phi(n)=(p
Re: (Score:3)
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 [slashdot.org].
Re: (Score:3)
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: (Score:3)
there aren't any crypto algorithms in use whose security rests on P != NP.
You mean except RSA?
Re: (Score:3)
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 po
Re:I'll be first to say WTF (Score:4, Funny)
Re: (Score:2)
Re: (Score:3, Insightful)
Math is a big part of a CompSci degree now-a-day.
lolwut? Since when has math NOT been a big part of computer science when computer science is a branch of mathematics? You must conflate computer science with programming or software engineering.
Your Math is Minimal (Score:3)
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 c
Re: (Score:2)
Re: (Score:2)
Okay... fair enough...
Outside of quantum computers, do nondeterministic turing machines even exist?
Re: (Score:2)
If n = 1, not just N == 1.
Re: (Score:2)
Damn HTML. Let me try this in Fortran instead:
IF N .LE. 1, not just IF N .EQ. 1
Re: (Score:2)
Nope. There's a case where N can be any value.
Re: (Score:2)
P=NP IFF N is equal to 1.
QED
Next problem?
You're being silly, but I can think of one solution that works for any value of N, so I'm afraid you blew it.
Re: (Score:2)
P and NP are sets...
Re:Nice way to spread malware? (Score:5, Insightful)
. . .
"he's made source code available"
Since checking the algorithm requires reading the source code - I would assume he's not spreading the source code of malware, because all interested parties WILL BE TRYING TO UNDERSTAND THE SOURCECODE.
Re:Maybe 3-SAT isn't NP-complete (Score:4, Informative)
No.
Every NP-Complete problem is based off the fact that 3-SAT is NP-Complete (3-SAT was the problem used by Levin and Cook to introduce the concept of NP-Completeness). Ever since then, getting into the NP-Complete club has meant reducing 3-SAT to your problem of choice in polynomial time.
The theorem is actually fairly simple, but I can't remember it off the top of my head, and the wikipedia article doesn't help at all. Anyone care to update it?
Re: (Score:3)