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

1–10 of 85 posts

Jun Fukuyama's P≠NP Page

#1

Post by vznvzn »

a new serious proof claim on P!=NP has been put forward by a Phd mathematician/computer scientist Jun Fukuyama last July 1 and has received very little public attention since then.

http://www.linkedin.com/pub/junichiro-fukuyama/36/2b9/88b

rumor is that its been submitted to a journal. it uses a known plausible approach based on monotone circuit theory for which there are some long established existing proofs of circuit lower bounds (dating to a celebrated 1985 proof by Razborov). Fukuyama has published several papers in computer science. it would be great if the online community could give this some attention as with the Deolalikar proof from 2.5yrs ago.

Jun Fukuyama's P≠NP Page
junfukuyama.wordpress.com

Re: Jun Fukuyama's P≠NP Page

#3

Post by breakyerself »

Can we get a laymans explanation of what this is about? I understand what p np is, but don't really understand what this person is claiming. Is this some kind of claim about the overall concept of p np? Or proving a specific case?

Re: Jun Fukuyama's P≠NP Page

#4

Post by [deleted] »

breakyerself wrote: post #3

Can we get a laymans explanation of what this is about? I understand what p np is, but don't really understand what this person is claiming. Is this some kind of claim about the overall concept of p np? Or proving a specific case?

[deleted]

Re: Jun Fukuyama's P≠NP Page

#5

Post by nate_martin »

breakyerself wrote: post #3

Can we get a laymans explanation of what this is about? I understand what p np is, but don't really understand what this person is claiming. Is this some kind of claim about the overall concept of p np? Or proving a specific case?

I think he is showing the clique problem cannot be solved in polynomial time. Since clique is in NP and not P, P!=NP.

Re: Jun Fukuyama's P≠NP Page

#6

Post by notimetorelax »

breakyerself wrote: post #3

Can we get a laymans explanation of what this is about? I understand what p np is, but don't really understand what this person is claiming. Is this some kind of claim about the overall concept of p np? Or proving a specific case?

If I understand it right he showed that Clique cannot be solved in polynomial time, since any NP complete problem is at least as hard as Clique none of those problems can be solved in polynomial time. So he used Clique to draw general conclusion that P!=NP.

Re: Jun Fukuyama's P≠NP Page

#7

Post by SenorWilson »

breakyerself wrote: post #3

Can we get a laymans explanation of what this is about? I understand what p np is, but don't really understand what this person is claiming. Is this some kind of claim about the overall concept of p np? Or proving a specific case?

Basically prove/disprove a p-np problem can be solved(in polynomial time) then you've proved it for the rest of the p-np problems.

Re: Jun Fukuyama's P≠NP Page

#8

Post by akavi »

Tipzntrix wrote: post #2

I'm interested in knowing how many of you on here are going to read this in one sitting. Not that it would be sufficient to analyze it for bugs, but because you're that interested.

If I had the mathematical background necessary to understand it, I certainly would.

... and I really wish I did have the mathematical background. Anyone have any recommendations on how to go from a standard CS undergrad math background to being able to understand proofs like these?

Post reply on HN