Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Jun Fukuyama's P≠NP Page

junfukuyama.wordpress.com

Post reply on HN
Print view View original

61–70 of 85 posts

Re: Jun Fukuyama's P≠NP Page

#61

Post by vznvzn »

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…

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

Re: Jun Fukuyama's P≠NP Page

#62

Post by mdxn »

vznvzn wrote: post #60
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…

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.

Re: Jun Fukuyama's P≠NP Page

#63

Post by alwaysright »

There is a great udacity course with all the background to the P/NP problem: http://www.udacity.com/overview/Course/cs313/ I found it very informative. It also has a section on "should you try solving the P vs. NP problem" and the answer is "not unless you have a lot of time, money, and though of something no one tried before, or is a math / CS professor"

Re: Jun Fukuyama's P≠NP Page

#64

Post by mdxn »

vznvzn wrote: post #61
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…

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

Re: Jun Fukuyama's P≠NP Page

#65

Post by vznvzn »

mdxn wrote: post #64
vznvzn wrote: post #61

Earlier quoted context omitted.

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

Re: Jun Fukuyama's P≠NP Page

#66

Post by vznvzn »

mdxn wrote: post #62
vznvzn wrote: post #60

Earlier quoted context omitted.

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…

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

Re: Jun Fukuyama's P≠NP Page

#67

Post by mdxn »

scott_weber wrote: post #59
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…

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

Re: Jun Fukuyama's P≠NP Page

#68

Post by mdxn »

vznvzn wrote: post #66
mdxn wrote: post #62

Earlier quoted context omitted.

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…

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

Re: Jun Fukuyama's P≠NP Page

#69

Post by vznvzn »

mdxn wrote: post #68
vznvzn wrote: post #66

Earlier quoted context omitted.

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

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

Re: Jun Fukuyama's P≠NP Page

#70

Post by mdxn »

morsch wrote: post #35
GoGoGalois wrote: post #33

Earlier quoted context omitted.

If a problem is NP complete then there is an algorithm to solve it in nondeterminstic polynomial time. Any nondet algorithm can be transformed to an exp poly time algorithm (just run through each of your poly time algorithms one by one) so showing CLIQUE has an exp algorithm doesn't help at all. We want a lower bound.

Yes, that's what he is saying, every CLIQUE algorithm takes at least exponential time.

No, he is claiming that l-CLIQUE requires exponential circuit size (this is the reason that most of the proof talks about circuit complexity and not time bounded Turing Machines). This is not necessarily the same thing as exponential time.
Post reply on HN