3 ms·

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

by mdxn 14y ago

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.

vznvzn 14y ago
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....
scott_weber 14y ago
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).
- mdxn 14y ago
  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
vznvzn 14y ago
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
- mdxn 14y ago
  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.
  - vznvzn 14y ago
    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....?
    - mdxn 14y ago
      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.
      - vznvzn 14y ago
vznvzn 14y ago
"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...
- mdxn 14y ago
  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.
  - vznvzn 14y ago
    oops. thx for info. didnt notice that. new to this. sorry for multiple replies that should just be edits.
sold 14y ago
> 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.
- mdxn 14y ago
  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".

by mdxn 14y ago

vznvzn 14y ago

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

scott_weber 14y ago

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

mdxn 14y ago
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

vznvzn 14y ago

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

mdxn 14y ago
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.
- vznvzn 14y ago
  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....?
  - mdxn 14y ago
    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.
    - vznvzn 14y ago

vznvzn 14y ago

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

mdxn 14y ago
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.
- vznvzn 14y ago
  oops. thx for info. didnt notice that. new to this. sorry for multiple replies that should just be edits.

sold 14y ago

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

mdxn 14y ago
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".