Slashdot Mirror
Claimed Proof That P != NP
morsch writes "Researcher Vinay Deolalikar from HP Labs claims proof that P != NP. The 100-page paper has apparently not been peer-reviewed yet, so feel free to dig in and find some flaws. However, the attempt seems to be quite genuine, and Deolalikar has published papers in the same field in the past. So this may be the real thing. Given that $1M from the Millennium Prize is involved, it will certainly get enough scrutiny. Greg Baker broke the story on his blog, including the email Deolalikar sent around."
I mean, NP has an N in front of the P. That's obviously not the same as P. Also, P != HP.
I was a afraid he might have left out an important step.
Anyone who loves or hates any language, platform, or manufacturer, doesn't know what they're talking about.
What would the impacts of this be for cryptography?
from a theoretical point of view at least?
I was under the impression that a lot of cryptography was based upon the hope that P!=NP and while in practice this wouldn't change much about anyone acts it might have an impact on how people think about the old cryptology vs cryptanalysis race.
Off the top of my head, if P = NP, then a lot of cryptography like RSA and elliptic curve cryptography become, in principle, mathematically solvable. Much of their security is premised on the idea that their equations are prohibitively difficult to brute force because they're NP.
If this proof holds up, then RSA and ECC become provably secure in a way they weren't before.
Anyone who loves or hates any language, platform, or manufacturer, doesn't know what they're talking about.
Really, P = NP would have far reaching implications to security, essentially proving that method of security will never be secure. If it is P != NP, then that means that you can have problems which take longer than polynomial time to calculate but only polynomial time to verify. So, if the paper is true, then it doesn't really change a whole lot, except that now we know that some day there isn't going to be a trivial solution. I guess its good for cryptography.
GCS/MU/P d- s:- a-- C++++$ UL++ P+ L++ E+ W++ N o K- w--- O M+ V- PS+++ PE Y+ PGP t+ 5- X R++ tv+ b++ DI++ D++ G+ e++ h-
At a 100 pages its going to be a while before I can say I have RTFA, but I'll get back with any relevance in a few days after I have digested it. I suggest any post claiming other wise are a bit hasty.
You can read section one (the introduction) and get a high level walk through of what he's doing. Just be prepared to have a requisite in the following to make it through that:
In order to apply this analysis to the space of solutions of random constraint satisfaction problems, we utilize and expand upon ideas from several fields spanning logic, statistics, graphical models, random ensembles, and statistical physics.
My computer science, math and statistics are still fairly sharp but the physics and graph theory are a bit much. Indeed this will take a while to digest. If he hasn't made a mistake in something like bridging together least fixed point logic and functions with Markov-Gibbs properties (correspondence and equivalence).
On the one hand it seems this will take a general expert in the math related sciences to verify but on the other you would think that -- like with the E8 and Lie groups -- this sort of proof would require a rather large unified theory to be able to reduce the N=NP? problem down to a provable situation. I'm no expert and it's been three or four years since I've even been in academia but even the subsections of this paper are noteworthy if they are true. It could be we're looking at something that jumps so far ahead like the famous papers of Turing and Shannon.
My work here is dung.
Of course they're not equal. It is revealed in Futurama episode 2-07.
The C&D letter is in the mail, buster. -Kool-Aid Man
You can still solve NP problems, just not in polynomial time. There ARE solutions to travelling salesman, just not fast ones...
GCS/MU/P d- s:- a-- C++++$ UL++ P+ L++ E+ W++ N o K- w--- O M+ V- PS+++ PE Y+ PGP t+ 5- X R++ tv+ b++ DI++ D++ G+ e++ h-
Practically, not much. It means we can breathe easy that a lot of crypto out there is now provably secure. It's been long considered likely that P != NP, because a lot of NP-complete problems are very old and nobody has gotten very far in solving them, and the extra focus in the last 40 years in breaking public key crypto hasn't produced much more progress on the problem. It was just the nagging issue of nailing down a proof.
A proof that P = NP would have resulted in a lot of cryptographers committing Seppuku. The contrary proof doesn't have many huge implications, though.
Not a typewriter
"Deolalikar's result is that "P (does not equal) NP (intersect) co-NP for Infinite Time Turing Machines". This is a special context - infinite time Turing machines are not the same thing as standard Turing machines, but are a kind of hypercomputer. Dcoetzee 09:07, 8 August 2010 (UTC)"
From http://en.wikipedia.org/wiki/Talk:P_versus_NP_problem#Potential_Solution
That was a different paper, published in 2005:
http://portal.acm.org/citation.cfm?id=1185240
It means we can breathe easy that a lot of crypto out there is now provably secure.
Wrong. It doesn't prove that there is no faster factoring algorithm.
If this has appeared somewhere in the other comments, sorry for missing it, but http://xkcd.com/664/ seems oh so appropriate here. (especially the alt text)
I meant asymmetric, which is what RSA is. Symmetric keys are usually exchanged relying on the discrete logarithm problem (RSA problem), not the integer factorization problem.
There are fast solutions to the TSP, they're just not fast in pathological cases.
If I were a cryptographer, I'd be positively itching for someone to break RSA. A 30 year old univerally-used secure cryptosystem means no job. :)
In a world where no crypto is really secure, everyone hires their own cryptographer to build a custom cryptosystem. Let's see Bletchley Park mathematicians try to cleverly crack gigabytes of junk encrypted data when the keys wouldn't fit in all the notebooks required to fill their entire building floor to ceiling.
At a 100 pages its going to be a while before I can say I have RTFA, but I'll get back with any relevance in a few days after I have digested it. I suggest any post claiming other wise are a bit hasty.
Aren't the best theories supposed to be elegantly simple? This looks a mess.
Wait.. that's just how my head feels after reading the abstract.
Yeah baby, we can now create an efficient way to break AES256 and decrypt the Wikileaks "insurance" file!
Pictures, er, I mean, peer review, or it didn't happen.
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
Off the top of my head, if P = NP, then a lot of cryptography like RSA and elliptic curve cryptography become, in principle, mathematically solvable. Much of their security is premised on the idea that their equations are prohibitively difficult to brute force because they're NP.
If this proof holds up, then RSA and ECC become provably secure in a way they weren't before.
The security of RSA is based on the idea that it is very difficult to factor large integers. However, this has not been shown to be an NP-hard problem and so really doesn't have anything to do with this.
Large integer factorization has not been shown to exist in NP-Complete (it is doubtful it does), it is know to exist in both NP and co-NP, it could exist in P (but it is doubtful) we just don't know. RSA public key crypto depends on the difficulty of factoring very large numbers. Currently there is no known efficient mechanism for determining the factors of a very large number. If P != NP we don't get a whole lot more than we have at the moment because we don't know exactly what complexity class integer factorization lives in. If P == NP then we have a serious problem because that requires there to be an efficient integer factorization algorithm. It is interesting that if P != NP we could very well end up in a situation where there are problems that have no efficient solution (not in P) but are not in the class NP-Complete (the "hardest" of the problems in NP). Integer factorization could very likely fall within this area.
I think this is the first time a serious researcher publishes a paper through email. Makes me wonder if he is actually publishing it or just asking for peer-review from his colleagues.
Or maybe he is trying to best Perelman in insanity. After all, even Perelman put the paper in arXiv.
Anyway, about the paper itself; I am a physicist, and he does say correct things about the Ising model and phase transitions. Unfortunately, it is only a small part of his proof that I can grasp. So I think he is dead serious.
Also, nice typography.
entropy happens
Really, P = NP would have far reaching implications to security, essentially proving that method of security will never be secure. If it is P != NP, then that means that you can have problems which take longer than polynomial time to calculate but only polynomial time to verify.
I think it's important to realize that even if they are "unresolved problems" of mathematics, it's not like both answers are equally likely like the flip of a coin. For example the Riemann hypothesis states that all non-trivial zeros of the Riemann zeta function have real part 1/2. It's true for every non-trivial zero we've ever found, but it's not proven true for all the infinitely many zeros. However, outside of mathematics a proof it's true will be met with "yeah, that's what we thought" and a proof it's false with "OMG what's going on here?". Another example is the prime twin conjecture, are there inifinte pairs like (3,5) (5,7) (11,13) (17,19) and so on. There's very good reason to believe it's true but nobody has able to formally prove it. There's a lot of problems today that appear to support the idea that P != NP, and that's what most people believe the answer is. However, stringing together formal proof that it's so is much harder. If this paper turns out to be true, surely it's a great leap for mathematics but it's the answer that doesn't change the world.
Live today, because you never know what tomorrow brings
Don't think this is what it means. Look at FFT (logarithmic optimization to a quadratic problem). P = NP as I understand it means that ALL NP problems have a corresponding P solution. You just have to think hard enough to find it. Proving that there are classes of NP that have no P just suggests certain crytographic algorithms MIGHT be NP. But it doesn't prove it (unless it was one of the particularly proven NP classes in this or some other paper). And even if this paper includes RSA / ECC, etc. That doesn't mean someone even more clever 30 years from now finds a flaw or special case where this isn't true and thus finds a P cracking tool.
-Michael
I recall reading that Minesweeper was an NP complete, or at least NP Hard problem. Doesn't P mean that a solution is computable is a reasonable time? If that's the case, then P!=NP by minesweeper.
Imagine you're almost done with a game of Minesweeper. 5 mines left. Your grid looks like this:
+----
| * * 2
| * * 3
| * * 2
| 2 2 1
Now, obviously each of the blocks on the outside, four of them, are mines. Which leaves two that you have no information about and can't _GET_ any information about. Which of the remaining two blocks is a mine?...
Would this be an example of P != NP, assuming Minesweeper is NP?
At the time of writing, there are two comments on Greg Baker's blog, congratulating Vinay on making it onto Slashdot. Jeez...he's potentially solved one of (if not) the most important open problem in computing, which could land him a million dollars in prize money...but yeah...well done on making it into that most esteemed of online publications, Slashdot.
Are you raving mad?
Of course there will be an error with this proof. Many errors, actually. Most of them irrelevant.
Maybe one of them is not. You know what? It will be caught in peer-review, exactly as it's been happening in the last centuries.
There's a reason noone uses formal proofs in mathematics. They're dull. They're slow. And we trust peer-review (for correctness, anyway).
What would be the use of a proof that no human can understand?
entropy happens
You forgot 'and I'm lazy'. Because NP is just hard, not impossible.
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
It's funny how we don't hear anything from HP for ages, then as soon as there's a sex scandal involving the disgraced CEO, out come all sorts of distractions.
I smell a rat. Okay, I smell 2 rats - Mark Hurd (ex-CEO) and HPs' spin department.
No, there really are solutions (not approximations) for many NP-complete problems that are fast on most inputs. For example, current SAT algorithms are fast on most instances. There are, however, pathological cases on which the algorithms are slow. The fact that a problem is NP-complete just means that, if P!=NP, there is no algorithm that is guaranteed to be polynomial-time for all inputs. It is still quite possible to devise algorithms that are fast for almost all inputs, but slow on a few pathological ones.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
But the margin is too narrow to contain it.
If you can read this, it means that I bothered to log in.
Correct sir, it should only ever contribute to karma instead.
Invaders must die
On what basis can you claim that P=NP is slipperier, given that FLT took 360 years to prove, and we've only been on it for 70 odd years so far?
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
Now that, my friend, is +5, Funny. Nothing here has been fixed in years.
I agree scribd sucks. You can find a link to the PDF from this page which also collects other proofs of P = NP, as well as proofs of P != NP. Pick whichever you prefer :)
http://en.wikipedia.org/wiki/P_versus_NP_problem#Consequences_of_proof
Consequences of proof
One of the reasons the problem attracts so much attention is the consequences of the answer. A proof that P = NP could have stunning practical consequences, if the proof leads to efficient methods for solving some of the important problems in NP. It is also possible that a proof would not lead directly to efficient methods, perhaps if the proof is non-constructive, or the size of the bounding polynomial is too big to be efficient in practice. The consequences, both positive and negative, arise since various NP-complete problems are fundamental in many fields.
Cryptography, for example, relies on certain problems being difficult. A constructive and efficient solution to the NP-complete problem 3-SAT would break many existing cryptosystems such as Public-key cryptography, used for economic transactions over the internet, and Triple DES, used for transactions between banks. These would need to be modified or replaced.
On the other hand, there are enormous positive consequences that would follow from rendering tractable many currently mathematically intractable problems. For instance, many problems in operations research are NP-complete, such as some types of integer programming, and the travelling salesman problem, to name two of the most famous examples. Efficient solutions to these problems would have enormous implications for logistics. Many other important problems, such as some problems in protein structure prediction are also NP-complete;[15] if these problems were efficiently solvable it could spur considerable advances in biology.
But such changes may pale in significance compared to the revolution an efficient method for solving NP-complete problems would cause in mathematics itself. According to Stephen Cook,[4] ...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.
Research mathematicians spend their careers trying to prove theorems, and some proofs have taken decades or even centuries to find after problems have been stated - for instance, Fermat's Last Theorem took over three centuries to prove. A method that is guaranteed to find proofs to theorems, should one exist of a "reasonable" size, would essentially end this struggle.
A proof that showed that P NP, while lacking the practical computational benefits of a proof that P = NP, would also represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P NP, much of this focusing of research has already taken place.[16]
Mit der Dummheit kämpfen Götter selbst vergebens
That's one hell of a spin department.
Some university really should hire them, because if they can prove P!=NP just to cover up a sex scandal, imagine what they could do if they didn't waste time writing press releases.
It is sortof a negative result. It has been known for forty years that many (10,000s) of difficult problems share a common difficulty, that makes them prohibitive to solve: NP-completeness. It was proven in the 70s that if you can solve one NP-complete problem fast, you can solve them all fast. This new result claims to prove that you cannot solve any NP-complete problem "fast". Some nerdy NP-complete problems are, for instance: how to make a certain circuit (CPU) using as few NAND gates as possible (i.e. faster hardware cheaper) or how to wire your motherboard as efficiently as possible (both how to draw the wires, and how to place the components). This says that it might ake more than a human lifetime (or Sun's) lifetime to solve any NP-complete problem. Some would like to see it as good news for cryptography, since it make some ciphers provably hard (however I am not aware of any such cipher -- unless it is proven that RSA is in NPC or in NPI).
Luckily 59 scholars have already proved either P=NP or P!=NP: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm In short: kdawson strikes again.
If you show P=NP by constructing an algorithm which solves an NP-complete problem in polynomial time, you immediately have a polynomial time algorithm for *any* problem in NP. That's the definition of NP-complete: a language is NP complete if any other language in NP can be reduced to it in polynomial time.
Even if you provide a non-constructive "existence" proof, it turns out you can construct an (incredibly awful!) polynomial time algorithm by, essentially, a brute force simulation of turing machines -- so it's not actually possible to provide a truly non-constructive proof that P=NP.
Not much, really. P != NP was the widely expected answer, it was just an unproven assumption. The fields that are affected have been proceeding as if P != NP was correct.
The point is that if P did = NP, then there wouldn't be any reason to think further about whether RSA is an NP problem. The constants might be huge, but there would clearly exist a poly-time algorithm for solving it. If P != NP as this result claims, then there may not be one, which is what cryptographers hope.
Net result: post is +5 funny but you take major karma hits.
"We used to rate people -1 Overrated. Now we just rate them +1 Funny. It's more effective that way."
(Apologies to KMFDM...)
"Convictions are more dangerous enemies of truth than lies."
If this proof holds up, then RSA and ECC become provably secure in a way they weren't before.
Note to self: Buy a 5$ wrench.
I don't mind dating a girl that has been with everybody, as long as she had a good shower afterwards.
World Health Organization?
You are entitled to your own opinions, not your own facts.
We'll know that P != NP if it takes us less time to verify the proof as it took him to generate it.
The theory IS simple. P!=NP. Easy.
Proofs, though...proofs can be complicated.
Even if P=NP, polynomial solutions requiring time n^99 consume enough time to be practically infeasible. Thus, even P=NP would not harm cryptography much, if it did not provide very efficient solutions for every NP-hard problem. On the other hand, favorite cryptographic hard problems, such as factoring, are not known to be NP-hard and may well turn out to be solvable in polynomial time, even if P!=NP. Therefore, proof that P!=NP won't have any interesting implications for cryptography unless it contains new ideas that can help in other ways. Neither will proof P=NP unless it includes ideas for fast solutions of interesting problems, such as fast factoring or fast discrete logarithm. Proof of P!=NP may help to solve another interesting problem in cryptography: one-way functions. Right now many results are built on the assumption that such functions exist, but nobody have found a single provable one-way function (easy to compute, infeasible to reverse). A bunch of functions are believed to have this property, but not a single one has been proved difficult to reverse. I would be interested to see if this proof will produce such an animal - a provably one-way function.
Sorry, I wasn't clear. I meant what's the next big problem in computer science.
Assuming this proof holds up, the next set of questions are how much the complexity hierarchy breaks down. There are a host of complexity classes between P and NP. Other important classes include PP and BPP http://en.wikipedia.org/wiki/BPP, http://en.wikipedia.org/wiki/PP_(complexity). BPP is a subset of NP and is tentatively believed to be equal to P. Another important class is BQP http://en.wikipedia.org/wiki/BQP which is the class of problems which can be solved quickly by a quantum computer. If this proof goes through it may generalize to showing that some of these other classes are distinct (proving that BQP is not equal to P would be almost as big a deal as proving that P !=NP).
No, I don't think so. Proving P=NP just means that some polynomial-time algorithm exists to solve any problem that can be verified by a polynomial-time algorithm. It doesn't necessarily tell you how to find such an algorithm,
You don't need to simulate the Turing machine. You just need to encode it as a boolean formula. That's part of what Cook's theorem shows; it shows how to encode a non-deterministic Turing machine as a boolean formula with at most a polynomial increase in size. Now that the problem is in a NP-complete form just follow the reductions until you get to the NP-complete algorithm that has a P algorithm. In this way you can solve any NP problem in P time as long as you solve one NP-complete algorithm in P time.
Chris Mesterharm
I think you are misunderstanding what the P=NP question means... and I don't blame you. The question itself is very "meta", but it is not self-referencing as you believe.
P is a set of questions (YES/NO questions) that can be answered easily. NP is another set of questions, that may or may not be easy to answer, but when you see the answer (YES/NO) and a proof for the answer, you can easily check if the proof is correct. But the question "P=NP?" doesn't belong to either of the sets. If P=NP, then all problems that are easily "verifiable" are also easily "solvable", and if P!=NP, then there are problems easily verifiable but hard to solve. But, as the question "P=NP?" doesn't belong to P or NP, there is no paradox.
That's an over simplification, of course. For instance, "easy" in the previous paragraph actually means "solvable in polynomial time by a deterministic turing machine", and "not easy" would be "solvable in polynomial time by a non-deterministic turing machine", and there is the widespread confusion about "NP" meaning "Non-P" instead of "P in a Non-deterministic machine". The wikipedia article is really good, but unfortunately, much too formal to understand without previous knowledge. I hope I helped a bit.
A Turing machine has a state (from a finite list of possible states), a table of operations to be performed based on input and state, and an input - nominally considered an infinite tape preloaded with an input string (a series of symbols from a finite set) with the remainder blank. Input symbols can be data or action symbols (data or program). The machine proceeds from its initial state processing operations from its table based upon its state and input until it finds a state that's "Accepting", and halts. A problem is considered soluble by a TM if any potential input, operated upon by the machine in exact accordance with the table can move the state to an "Accepting" state. For the purposes of Turing Machines, operations take 0 time and the machine is immortal. From the beginning these are not presumed to be mechanical or electronic machines, but rather a theoretical human who executes the instructions without any bias or thought to the outcome. Turing Machines are a thought experiment, not physical machines. They are hypothetical. They are, however, widely used in information theory as well as other fields including physics.
/Non Sequitur: Alan Turing was a Brit who confessed to being queer, was chemically castrated and deprived of his security clearance as punishment, and is supposed to have killed himself at 42 with an apple laced with arsenic, a-la Snow White. We'll never know what more he might have given us. Homophobia cost us one of the greatest minds of the 20th century. His work is now considered fundamental to our understanding not only of what computers can do, but of the nature of the universe.
A Deterministic Turing Machine (DTM) is one that has at most one action for a specified state, action symbol and input. A Non-Deterministic Turing Machine (NDTM) may have more than one.
To say that P!=NP is to say that the Non-Deterministic Turing Machine can find an Accepting state that the Deterministic Turing Machine can not.
In the case of a NDTM with more than one potential action to be performed for a specific state and action the Turing Machine (TM) can be considered to clone itself, which each clone performing one of the indicated actions - in essence creating a tree of potential Turing Machines. Alternately the Turing Machine can be assumed to select the action that results in the Accepting state if there is any. AFAICT the potential for input strings to come to the Accepting state on divergent paths is moot as any Accepting state will do, and in the case where divergent "leaf" TMs Accept the input or enter infinite loops, an Accepting TM wins. This isn't an input validation routine: the determination that the input is invalid is an Accepting state.
I haven't read TFA, but I would imagine that the proof for P=NP would involve finding one problem where the non-deterministic machine found a solution that a deterministic machine couldn't. Presumably this involves solutions hidden by infinite loops.
Really, the idea is silly though. It's Garbage In, Garbage Out. If your Turing Machine needs non-determinism it's because it's potentially operating on unknown data or processes and so its state/action table is inadequately defined. This is an abuse of the machine. It results in solutions for problems that are NP, but the only rational course is then to dissect the tape, find the successful branches of potential choices, find the unknowns and rebuild the machine's state/action table to include these potentials. We call this process "the scientific method". To fail at this, the unknown thing that caused the effect must be unknowable. In fact, any such Turing Machine can be redefined to permute across potential state/action/input triplets, or to include the reconciliation of the result to the process, and the question devolves into the halting problem, so the problem becomes the impossibility of iteration against possible out
Help stamp out iliturcy.
IMO, The P vs NP is fundamentally more tricky than other famous theorems/conjectures (like FLT), because on some level it is a statement about mathematics itself. The assumption that P != NP on some level implies that the finding mathematical proofs is difficult. This means that if P!=NP it may be even more difficult to prove that P!=NP. It has been shown that assuming one-way functions exist (this would imply P!=NP easily enough) that a certain type of proof called "natural proofs" can never be used to separate P from NP.
On the flip side, showing P = NP could be easier, but most people believe this is false, since it would mean that there is essentially one "master algorithm" that can solve any problem in NP efficiently.
The current state of computational complexity theory is that we are no where close to resolving P!=NP, that is unless this proof actually checks out. Honestly, we can't even settle "easier" questions like P vs PSPACE. The implications of a correct proof would be absolutely mind blowing.
Indeed, N)on-P)eer-reviewed does not equal P)eer reviewed.
But B)eautifully L)aTeXed trounces peer review.
That's one hell of a spin department.
Some university really should hire them, because if they can prove P!=NP just to cover up a sex scandal, imagine what they could do if they didn't waste time writing press releases.
Oh man, if you think the politics and backbiting are bad in typical academia, wait until you see an entire computer science department arguing over who gets to have illicit sex in order to set off the proof-generating team.
"This algorithm runs in constant time. Come on, 2,147,483,648 is a constant..."
A simple description is that there are problems where you can quickly figure out that a given solution is correct, but where it takes a very long time to actually find a solution. There's a nice description here: http://www.claymath.org/millennium/P_vs_NP/
Well ok, but doesn't this depend on whether you consider a theory Not Particularly Complete without a proof?
Bazinga.
I'm being thick here I guess, but why do we know the required simulation of Turing machines to be in NP=P (given assumption), and not EXPTIME or at least PSPACE?
The algorithm is: on iteration N, simulate one (more) step on Turing machines 1 through N. Stop when a machine outputs an answer with a formal proof that answer is correct.
If P = NP, then the M'th Turing Machine does this in P(n) steps. It takes P(n)+M iterations before that happens. Each iteration takes M+i steps, so the run time is O(P(n)^2), which is polynomial! (note that M is an "exponentially large" constant, so this approach wouldn't result in a truly usable algorithm.)
Currently the best factoring algorithm is GNFS, which can factor in exp( ( n * log^2(n) )^(1/3) ). However, that's still exponential because it's greater than exp(n^(1/3)).
The paper claims a deterministic time lower bound for the hardest problems in NP^CoNP at exp( log^k(n) ). I'm sure this paper will spur research into algorithms with expected runtime of exp ( log^k(n) ), and that should quickly give us a faster factoring algorithm.
On a personal note: I developed a SAT algorithm in 2005, and my rudimentary analysis showed that it requires at least exp( log^2(n) ) for NP^CoNP. I never bothered to compute the upper bound because I gave up on it once I realized I couldn't use it to prove a lower bound for NP. However, I may have to dust off the algorithm and solve the upper. This paper gives me hope that it's exp( log^k(n) ), which would give a better result for factoring than GNFS. :-)
Keep dreaming.
Even at "Harbor Freight" (read: cheap-ass tools), a $5 wrench won't do much more than let you take the wheels off a model train and pick your nose.
Go for the $10 wrench. ;)
"I’m dead serious—and I can afford it about as well as you’d think I can." See his blog.
The Millennium Prizes mostly have different rules for proofs and counterexamples. That's not the case for P=NP, though; either proving P=NP or P!=NP is sufficient to get the prize (given that the proof is confirmed valid, etc.).
(1)DOCOMEFROM!2~.2'~#1WHILE:1<-"'?.1$.2'~'"':1/.1$.2'~#0"$#65535'"$"'"'&.1$.2'~'#0$#65535'"$#0'~#32767$#1"
...because if they can prove P!=NP just to cover up a sex scandal, imagine what they could do if they didn't waste time writing press releases.
Hold the best orgy ever?
Rampant carbon sequestration destroyed the Dinosaurs' tropical paradise. I'm here to help repair the damage.
Ah, but there are more of us now. If it took 1 billion people 3650 years to solve, it should take 6 billion people a mear 60 years. The fact it has take 70 already clearly shows the added cycles this calculation requires.
Humanity follows basically the same logic as massively parallel supercomputers.
Being a researcher in Finite Model Theory (FMT) this paper is very interesting because it uses ideas from that area, i.e. the LFP(FO) bits. Reading through the proof synopsis and scanning the FMT sections there are several potential pitfalls:
It is already known that LFP(FO) on unordered structures is a proper subset of LFP(FO) on order structures, so if the ordering and order-invariant requirements for LFP(FO) = P are not dealt with in the proof, then all the author has done is proof that LFP(FO) on unordered structures is a proper subset of NP. Which is already known.
Another potential problem is in the arguing that all first-order properties are local (Hanf's Theorem) in the presence of ordering, as every vertex is effectively connected to every other vertex (Immerman's proof of LFP(FO) = P requires total ordering of the underlying graph/structure), and hence every vertex is in the radius = 1 neighbourhood of every other vertex.
The crucial step in the proof, appears to be the argument that no LFP(FO) formula can extend a partial solution to k-SAT to a full solution to k-SAT. This is where I'd check the logical steps of the proof, and also make sure that the ordered nature of LFP(FO) structures is correctly considered.
I look forward to seeing this published in a peer-reviewed mathematics journal: I'd recommend to the author the "Journal of the ACM" for this (as it's one of the best journals in the field).
That fishy smell, it's from the sex scandal.