3 ms·

P/Poly is NOT polynomial depth circuits. it is you that is mistaken about this complexity class characterization. it is polynomial SIZE circuits. other statemen

by 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
      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....
  - sold 14y ago
    No. P/poly is uncountable (contains every unary language) and NP, NEXP, R etc. are countable.

by vznvzn 14y ago

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
    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....
- sold 14y ago
  No. P/poly is uncountable (contains every unary language) and NP, NEXP, R etc. are countable.