8 ms·
Jun Fukuyama's P≠NP Page
a new serious proof claim on P!=NP has been put forward by a Phd mathematician/computer scientist Jun Fukuyama last July 1 and has received very little public attention since then.
http://www.linkedin.com/pub/junichiro-fukuyama/36/2b9/88b
rumor is that its been submitted to a journal. it uses a known plausible approach based on monotone circuit theory for which there are some long established existing proofs of circuit lower bounds (dating to a celebrated 1985 proof by Razborov). Fukuyama has published several papers in computer science. it would be great if the online community could give this some attention as with the Deolalikar proof from 2.5yrs ago.
- albertzeyer 14y agoBtw., what about Vinay Deolalikar's proof now? The last update I could find: http://rjlipton.wordpress.com/2011/08/11/deolalikars-claim-one-year-later/ http://rjlipton.wordpress.com/2011/08/11/deolalikars-claim-o... http://news.ycombinator.com/item?id=2891710 http://news.ycombinator.com/item?id=2891710
- iso-8859-1 14y agoIt is incorrect. I guess that after he realized it himself, he got discouraged and didn't bother to tell people about it.
- Tipzntrix 14y agoI'm interested in knowing how many of you on here are going to read this in one sitting. Not that it would be sufficient to analyze it for bugs, but because you're that interested.
- akavi 14y agoIf I had the mathematical background necessary to understand it, I certainly would. ... and I really wish I did have the mathematical background. Anyone have any recommendations on how to go from a standard CS undergrad math background to being able to understand proofs like these?
- adamnemecek 14y agoThis book is a good start http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X/ http://www.amazon.com/Introduction-Theory-Computation-Michae...
- ibejoeb 14y agoSipser is great. Highly recommended. Working that book really accelerated my understanding. You can go from practically nothing to something with it, though it helps to have some discrete math.
- Tloewald 14y agoRead it and google as you go. Math is one of the best covered topics online. For a potential millenium prize proof, it seems very approachable. That said, that's not saying much.
- evincarofautumn 14y agoAs a compiler guy, I found that reading a lot of type theory papers helped me really get into the CS theoretical mindset, which made reading mathematics papers a lot easier. Writing a lot of Haskell code didn’t hurt. Oleg Kiselyov has some fairly approachable papers, as do Simon Peyton-Jones and Daan Leijen. Try searching for things on Lambda the Ultimate[1] if you’re interested. [1]: http://lambda-the-ultimate.org/ http://lambda-the-ultimate.org/
- tsahyt 14y agoI'm certainly missing some background but if I had the time I'd work my way through it just for the hell of it. The problem he attempts solving here is extremely important so I welcome any attempts made at it.
- breakyerself 14y agoCan we get a laymans explanation of what this is about? I understand what p np is, but don't really understand what this person is claiming. Is this some kind of claim about the overall concept of p np? Or proving a specific case?
- deleted 14y ago[deleted]
- nate_martin 14y agoI think he is showing the clique problem cannot be solved in polynomial time. Since clique is in NP and not P, P!=NP.
- cgray4 14y agoThe claim is that since clique is in NP-complete and not P, P != NP. (Every problem in P is in NP.)
- notimetorelax 14y agoIf I understand it right he showed that Clique cannot be solved in polynomial time, since any NP complete problem is at least as hard as Clique none of those problems can be solved in polynomial time. So he used Clique to draw general conclusion that P!=NP.
- btilly 14y agoI googled to see if Terry Tao had weighed in yet. He has not that I've seen. However http://vzn1.wordpress.com/2012/12/08/outline-for-a-np-vsppoly-proof-based-on-monotone-circuits-hypergraphs-and-factoring/ http://vzn1.wordpress.com/2012/12/08/outline-for-a-np-vsppol... suggests that this looks like a serious attempt. (Of course most serious attempts will fail.)
- gregtour 14y agoPosting in epic thread.
- thomasbk 14y agoA great site with 95 documented attempts at proving P ?= NP is over at http://www.win.tue.nl/~gwoegi/P-versus-NP.htm http://www.win.tue.nl/~gwoegi/P-versus-NP.htm, for those interested in the subject.
- B-Con 14y agoFrom other people's research ( http://michaelnielsen.org/polymath1/index.php?title=Jun_Fukuyama%27s_P%E2%89%A0NP_Paper http://michaelnielsen.org/polymath1/index.php?title=Jun_Fuku... ) he seems to have a credible background. Although I find it interesting that he works for Toyota: > My name is Jun Fukuyama. I’m currently a researcher at Toyota InfoTechnology Center. I’m visiting WINLAB and Civil Engineering department at Rutgers University, working on algorithms and mathematical analysis related to vehicular communications and mobility modeling. Unless he's been doing this research in his spare time, it seems like an odd fit for Toyota to dedicate research to. Obviously large companies employ theory-oriented researchers, but when I think Toyota I don't really think about very abstract computer science. I'm curious if there are any particular applications for the company one way or the other.
- tomjakubowski 14y agoToyota actually has opened a school in Chicago specifically for computer science, in conjunction with the University of Chicago: http://en.wikipedia.org/wiki/Toyota_Technological_Institute_at_Chicago http://en.wikipedia.org/wiki/Toyota_Technological_Institute_...
- jamesjporter 14y agoI go to UChicago; that place is sort of like an eerie mystery box that nobody ever goes to or talks about. I didn't even find out about it's existence until my 3rd year here. My one friend who's been in there described the experience as really bizarre; it left him half convinced that its actually a front for some sort of Israeli money laundering operation.
- gburt 14y agoHas this been submitted to a journal or the Clay Institute or any peer review yet?
- gburt 14y agoI wish I had the mathematical background to comprehend this. It's very involved. My understanding is that he has shown that CLIQUE (a known NP-complete problem) takes exponential time and thus is not solvable in polytime, this would mean there is a problem outside of P but inside of NP, and this P != NP.
- GoGoGalois 14y agoIf a problem is NP complete then there is an algorithm to solve it in nondeterminstic polynomial time. Any nondet algorithm can be transformed to an exp poly time algorithm (just run through each of your poly time algorithms one by one) so showing CLIQUE has an exp algorithm doesn't help at all. We want a lower bound.
- morsch 14y agoYes, that's what he is saying, every CLIQUE algorithm takes at least exponential time.
- GoGoGalois 14y agoOh ok, I thought the first post was referring to a single algorithm, not every possible algorithm. My mistake.
- gburt 14y agoSorry, if I could I would edit it to be more clear. We definitely need to show that no algorithm can exist with poly runtime for all inputs.
- mdxn 14y agoNo, he is claiming that l-CLIQUE requires exponential circuit size (this is the reason that most of the proof talks about circuit complexity and not time bounded Turing Machines). This is not necessarily the same thing as exponential time.
- kiskis 14y agodamn, there is a typo on page 32 (in paper version 1.11). Stopped reading. I'm wondering if that voids the proof. Let's the downvote begin.
- bowyakka 14y agoThis is why we cant have nice things
- kiskis 14y agonow the funny thing is that there is really a typo on that page, so all of the these hacker news people downvote just because I pointed out some small, but truth parth of reality. this is called witch-hunt
- Mouq 14y agoWell, sure. It's more that you posted a comment not that there's a typo but that this typo makes it so unbearable to read that you were simply forced to stop. But anyway...
- kiskis 14y agoit will be oil on fire, and you guys will already downvoted me into oblivion, but the truth is the same, the paper has several typos, which makes in unquestionable that it did not see a spell-checker.
- ColinWright 14y agoSpell checking math, and in particular LaTeX math, is a complete nightmare. I, for one, find that there are just as many substantive typographical errors after spell checking my papers as before, and all I've done is wasted at a minimum an hour trawling through false positives. Besides, small typos in a paper that's substantially readable and well crafted, written by someone in a language other than their first, are scarcely a reason to stop reading.
- ColinWright 14y agoVery briefly: Context: Some problems are easy, and known to be easy. Some problems appear to be hard, and yet easy to verify alleged solutions. That seems odd - let's have a closer look. Example: Consider being given a network and asked if there's a path that visits every node exactly once and returns to its starting point. (This is the task of asking if a Hamilton Cycle exists). If the network is big enough, deciding if this can be done can be really hard. However, checking if someone has successfully done it is easy. Motivation for a definition of NP: A problem for which it is efficient (for which read "polynomial") to check a purported solution is said to be in "NP". Knowing whether a Hamilton cycle exists in a network is one of many, many such problems. Definition: A problem is in "NP" if there is a polynomial time algorithm to test an alleged solution. Definition: A problem is in "P" if there is a polynomial time algorithm to solve it. Lemma: All problems in "P" are also in "NP". Proof left to the interested reader. (Note: technically we are dealing with Decision Problems - problems where the answer is always Yes or No. For example, I didn't ask you to find a Hamilton Cycle, I only asked if there was one. Sometimes the Decision version can be ramped up into actually finding the solution.) Note that easy problems (for example, finding a cycle that visits every edge exactly once - an Euler Cycle) is also "NP", but it's not a hard NP problem - it's actually in "P". This point confuses a lot of people. NP does not automatically mean hard - that comes in a minute. Another example: Similarly, factoring a large integer can be really hard, but if someone claims to have a factor, checking it is as easy as doing the division. Comparing problems: Cleverly, it can be shown that if you can solve the Hamilton Circuit problem efficiently, that can be converted into a way of solving the factoring problem. In some very real sense, the Hamilton Circuit problem is harder than (or equal to) the factoring problem. Finding: There are many, many NP problems that have been shown all to be equivalent to each other, all to be easy to check solutions, and yet no algorithm for solving in polynomial time known. Such problems are call NP-Complete (NPC) because an efficient algorithm for any of them will completely solve all the NP problems. So: * A problem is said to be in "P" if there is an algorithm that takes instances and produces answers in polynomial time. * A problem is said to be in "NP" if there is an algorithm that takes only polynomial time to check a purported solution for correctness. * It is unknown if there are any problems that are in "NP", but not in "P". That is the P vs NP question, and the Clay Mathematics Institute has offered $10^6 for its resolution. You could do this by showing that there is a polynomial time algorithm for any of the NPC problems, or by showing that no such algorithm exists. Summary: * P problems are "easy" * NPC problems are thought to be hard * There are lots of NPC problems, and solving any one of them would solve all NP problems. * Integer factoring (IF) is thought to be outside P, but not as hard as NPC. * There are problems that are harder than all NPC problems, these are called NP-Hard. So we think that P < IF < NPC={ Clique, 3SAT, G3C, Knapsack, Ham, ...} <= NP-Hard But we don't know if these are, in fact, all different. The submitted link is to a paper that says yes, they are all different. I hope that helps.
- vznvzn 14y agohi all. meant to post a comment but didnt understand this hackernews interface so far, am brand new to this site. fukuyama states on his web page he's worked on P vs NP for over 10 yrs, both inside and outside of his professional jobs which include research and teaching. the web page is a proof [claimed/attempt] that P!=NP posted on Jul 1. unfortunately its gotten very little to no online attention since then, at this point so far. he doesnt seem to have announced it anywhere in cyberspace, only created the blog.
- mdxn 14y agoIf you don't mind me asking, how and when did you find his blog post?
- Zircom 14y agoYES, YOUR MAJESTY!
- KaoruAoiShiho 14y agoAll Hail Britannia
- anandkulkarni 14y agoBefore anyone gets too excited, I would caution that there there is a long history of failed attempts at this problem, and an equally long history of premature announcements. On the surface, here is what is encouraging about this one: - The author is a theory professional and not an amateur or a crank - The author frames this as a possible proof where he's seeking feedback on the method, rather than declaring a solution up front - The author builds on existing theory in a formerly mainstream approach that has been shown to have problems (circuit lower bounds) - Looks like a serious and well-considered proof effort Here is why HN should hold off on any excitement: - This style of proof was found to be unworkable in the past. In particular, approaches to proving circuit lower bounds in this manner were shown by Razborov and Rudich to be "natural proofs" in the 1990s, which is a category of proof strategy that cannot demonstrate P/NP. It's not explained why this strategy does not succumb to the same problem -- though the author surely has some reasoning around it. (see point 6 of Scott Aaronson's "8 signs a proposed P/NP proof is wrong": http://www.scottaaronson.com/blog/?p=458 http://www.scottaaronson.com/blog/?p=458. You might also see this comment from /r/math: http://www.reddit.com/r/compsci/comments/14mqqt/anyone_have_the_math_to_check_out_this_p_np_proof/c7elwbz http://www.reddit.com/r/compsci/comments/14mqqt/anyone_have_...) ). - There is a very good community framework for evaluating proposed solutions when the author's ready. Possibly the author has already submitted the work to a journal, but it's not clear that he's confident enough yet to invite more active discussion on his effort from the theory community. I can't find any discussion of it online. It's likely he's pursuing these on his own, and conceivably flaws have been found since the summer. - The author does not declare this as a completed solution in the same way that Deolikar did two years ago. In that case, his announcement led to an analysis by the theory community online that led to discovery of core errors. We can wait here 'til the author gives a bit more information. - This proof joins dozens of other announced solutions to P/NP in both directions (see, for example, http://www.win.tue.nl/~gwoegi/P-versus-NP.htm http://www.win.tue.nl/~gwoegi/P-versus-NP.htm) which emerge quite regularly, and close attention paid to each will leave no time for original research :)
- vznvzn 14y agohi AK. maybe consider blogging about this? this is a well written but superficial analysis. scott aaronson insists on his blog that a proof should explain why it succeeds against "known barriers" eg razborov/rudich Natural Proofs. but this is really an optional requirement of a proof. moreover the actual barrier to "natural proofs" is very subtle and basically insists that a proof, if it exists, should have a certain "intrinsic complexity" in its constructions, and that many such constructions in the literature for class separations do not have this "intrinsic complexity". but new researchers are just suggesting that this only requires some new "intrinsic complexity" function that hasnt been seen before; but that such functions do exist, they just dont seem to be used in proofs that we know of. eminent authorities in the field such as Lipton have argued that the near 20yr old Natural Proofs may be overdramatized as a real barrier. here is liptons blog on the subj: http://rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natural-proofs/ http://rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natu... here is chow in AMS: "Nevertheless, it is my personal opinion that the optimistic approach is the right one; that is, the Razborov–Rudich result should be regarded as a hint, and not a barrier, to separating complex- ity classes. The only real barrier is our lack of imagination." http://www.ams.org/notices/201111/rtx111101586p.pdf http://www.ams.org/notices/201111/rtx111101586p.pdf
- jere 14y agoFor a popular treatment of the subject and the consequences, see this film (I assume the first film ever made about P=NP and it was released just this year): http://en.wikipedia.org/wiki/Travelling_Salesman_(2012_film) http://en.wikipedia.org/wiki/Travelling_Salesman_(2012_film) I just finished a section on NPC problems in my algorithms class (working on a masters). For years, I've been confused about the true meaning of P, NP, and NPC. Feels weird saying it, but I am so glad I've finally got a good grasp on at least the definitions. One of the most gratifying moments in the class was doing homework problems that required proving various problems were in NPC.
- mdxn 14y agoNote: For the moment, I will assume that the NP != NC and above results are correct enough to consider the validity of the latter portion of the paper. As far as I can tell (from my initial reading), the author (and many many commenters here) seem(s) to be confusing polynomial time (P) with polynomial circuit size (P/poly). These are completely different complexity classes in style and probably in power, too. Last time I checked, there was not a good characterization of P in terms of circuit complexity (the attempt at doing so is P/poly). So, logically, comparing P and NP is not even possible without additional knowledge about P. The exception to this being showing that X != NP where P <= X <= NP. For reference: P <= BPP <= NP We know that BPP (a randomized version of P) is (non-strictly) contained in P/poly. We also know that proving P = BPP (which is conjectured to be true by most) requires these classes require superpolynomial lower bounds for Boolean|Arithmetic circuit size. As far as I know, proving an exponential lower bound for an NP-complete problem doesn't immediately rule that P != NP since P !=> only polynomial size circuit size (the circuit size only relates to the size of the advice function). P might not contain problems that require exponential circuit size, but this fact is not stated, proven, nor reference by the author here. Simply put: The author assumes that P != NP follows immediately from Theorem 6.1. This is not as obvious as they might think it is; many additional details are needed. Admittedly, I have not rigorously studied or concluded anything from the flattening process the author proposes. I honestly don't believe I have to. Skimming over it, I don't see any way that P is characterized in terms of polynomial circuit sizes (which probably is an assumption as powerful as P!=NP) here. I also do not see any mention of P/poly, which I believe the author is attempting to use. For a paper approaching the P vs NP issue using circuit complexity, I would expect this much. Because of the lack of even a mention of BPP, P/poly, and others, I would be highly surprised if many of these results in the paper hold at all. Though, hopefully, I might be wrong. EDIT: Accidentally used circuit depth when I was really thinking of size.
- vznvzn 14y agohave not dug into the paper, but basically if it can be shown that NP cannot be computed with Poly-size circuits, then P!=NP, ie a weaker consequence of the stronger NP!=P/Poly. that is one of the basic conjectures of circuit theory, a stronger statement than P!=NP. the author may be talking about P-size circuits without mentioning the P/Poly class by name-- that would show some unfamiliarity with standard complexity theory, but is not a huge crime, and it is conceivably not necessary to actually refer to P/Poly in circuit proof referring to that class, although of course it would be better... P/Poly was originally defined w.r.t an Oracle, and arguably the equivalent characterization of that same class as "P-size nonuniform circuits" is actually much simpler & intuitive & natural....
- alwaysright 14y agoThere is a great udacity course with all the background to the P/NP problem: http://www.udacity.com/overview/Course/cs313/ http://www.udacity.com/overview/Course/cs313/ I found it very informative. It also has a section on "should you try solving the P vs. NP problem" and the answer is "not unless you have a lot of time, money, and though of something no one tried before, or is a math / CS professor"