Comment by mdxn | Hacker News Reader

Comment by mdxn | Hacker News Reader

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

"as far as I know, proving an exponential lower bound for an NP complete problem doesnt immediately rule that P!=NP". that statement is FALSE. P!=NP is exactly a consequence of proving exponential lower time bounds. actually P!=NP would be a consequence of even proving somewhat weaker superpolynomial time bounds on any NP complete problem...

I was clearly referring to exponential circuit sizes (note the sentence before it), not exponential time.

By the way, you can edit your original reply to contain more information rather than just making a bunch of new ones.

oops. thx for info. didnt notice that. new to this. sorry for multiple replies that should just be edits.

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

The depth vs. size characterization was a legitimate mistake of mine (got distracted by the authors use of depth). I am aware of the distinction. Though in writing my post, I did actually have size in mind. I'll edit to reflect this.

As for (P/poly != NP) => (P != NP), I have never heard of this. I have, however, seen that if NP is not a subset of P/poly then P != NP (which was not claimed here). Perhaps I am missing a stronger result? If so, please link me to a source for such a result.

thats what I meant. was writing P/poly != NP to mean "NP is not a subset of P/poly". or do we have to worry about the case where P/poly is a superset of NP? have never even considered that, have no idea what it would imply, think it might be impossible....?

We do have to worry about it. If it is the case that NP <= P/poly, then PH collapses to sigma P 2. Unless there have been recent results that show otherwise, P/poly might even contain NEXPTIME.

Regardless, the connection to P in this paper is not immediately obvious to me. It certainly is not explicitedly stated in a form that I even partially recognize.

Because of these reasons, I am deeply skeptical of the leap directly to P != NP. A lot of incorrect papers do something similar: They show a lot of very complicated constructions then, BAM, Collorary. P != NP. It kind of hand waves the most important step.

there are indeed dozens of incorrect papers which make neophyte errors. however, this one was written by a TCS Phd [from what I can tell] with a respectable number of published papers, some in TCS. I have studied this particular area of attack for many years, ie monotone circuit theory, & think it is one of the most plausible lines of attack on P vs NP, hence my playing devils advocate for this proof so far. even if there are holes, which frankly, is the most probable case, it may either prove something new about monotone circuit theory, and/or raise awareness/interest in this particular direction of attack.

would like to see the opinion of experts who know about monotone circuit theory, which is a deep area with very many substantial results & think there are few who are really qualified to judge these results. even Phds in complexity theory may not be very familiar with monotone circuit proofs.... they are some of the most complex, arcane/abstruse, but even award-winning proofs in TCS.... (hence some of their plausibility in attack).... it seems possible to me the author has avoided all the basic traps and that only some other experts in the area can find the holes after careful study....

and note in the paper that there is a big difference between assuming statements that cannot be proven, and outright false statements. the author may actually have some pieces of the proof that cannot be proven as he thinks, but are not known to be false, and these can be turned into new substantial conjectures! that is the process of mathematical development....

No. P/poly is uncountable (contains every unary language) and NP, NEXP, R etc. are countable.

Not sure if I'm labouring under basic misconception here (or if you're trolling). First, you note that BPP <= P/poly. Secondly, you note that it is hard to prove P = BPP, but this is not necessary, all we need is the trivial P <= BPP. Then P <= P/poly < NP (if the author is correct).

1. BPP <= P/poly was proven by L. Adleman.

2. I never said that P = BPP was hard to prove. I only brought up BPP because its derandomization, despite being limited to subexponential nondeterministic time, would still imply a lower bound of super polynomial circuit size (which could be the exponential lower bound presented by the author). The author is using this exponential lower bound (circuits) to immediately conclude that P != NP:

"The proof of Theorem 6.1 is now complete. We have: Corollary 6.5 P 6= NP"

Note: Theorem 6.1 is the lower bound

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

> For reference: P <= BPP <= NP

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

Reply on news.ycombinator.com