Jun Fukuyama's P≠NP Page

All Hail Britannia

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

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 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 For reference: P 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.

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

P/Poly is NOT polynomial depth circuits. it is you that is mistaken about this complexity class characterization. it is polynomial SIZE circuits. other statements of your post are incorrect. P !=NP does in fact follow as an immediate, direct consequence from P/Poly (ie poly size nonuniform circuits) != NP