Jun Fukuyama's P≠NP Page • Hacker News Board

Re: Jun Fukuyama's P≠NP Page

#81

Post by ColinWright » Tue, Dec 11, 2012, 4:38 PM UTC

kiskis wrote: post #80

Mouq wrote: post #78

Earlier quoted context omitted.

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

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

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

Re: Jun Fukuyama's P≠NP Page

#82

Post by sold » Tue, Dec 11, 2012, 4:46 PM UTC

mdxn wrote: post #56

Note: 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 ti…

> For reference: P No, BPP is not known to be in NP. It is known to be in Sigma_2 and Pi_2.

Re: Jun Fukuyama's P≠NP Page

#83

Post by mdxn » Tue, Dec 11, 2012, 5:33 PM UTC

sold wrote: post #82

mdxn wrote: post #56

Note: 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 ti…

> For reference: P No, BPP is not known to be in NP. It is known to be in Sigma_2 and Pi_2.

I can't edit to clarify now, but that statement is meant to be an assumption rather than of fact for use as a toy example for a line of reasoning.

If I could edit again, I'd make it read as "For instance, let P <= BPP <= NP".

Re: Jun Fukuyama's P≠NP Page

#84

Post by qdog » Tue, Dec 11, 2012, 6:03 PM UTC

cgray4 wrote: post #46

qdog wrote: post #43

Earlier quoted context omitted.

All NP problems can be converted into the other NP problems, therefore if you can prove it for one NP problem, you prove it for all NP problems.

You missed a few words. Any NP-complete problem can be converted into any other NP-complete problem in polynomial time.

Right, oops.

Re: Jun Fukuyama's P≠NP Page

#85

Post by anandkulkarni » Sat, Dec 15, 2012, 7:31 AM UTC

vznvzn wrote: post #54

anandkulkarni wrote: post #50

Before 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 solut…

hi 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…

I may have come across as insistent on clearly stating ways around the natural proofs barrier because this is Hacker News, where folks are liable to jump to conclusions, and not, say, http://cstheory.stackexchange.com. Given the large number of attempts against P vs. NP, frequently by folks who are not active in complexity theory, it's often better to try to understand these ideas on theory sites.

You make an reasonable point, vis-a-vis Chow; rather than being regarded as an absolute barrier for lines of reasoning involving circuit complexity, the requirement of being a sufficiently complex proof may provide a jumping-off point for uncovering a working method.