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

11–20 of 85 posts

Re: Jun Fukuyama's P≠NP Page

#11

Post by adamnemecek »

akavi wrote: post #8
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?

This book is a good start http://www.amazon.com/Introduction-Theory-Computation-Michae...

Re: Jun Fukuyama's P≠NP Page

#13

Post by B-Con »

From other people's research ( http://michaelnielsen.org/polymath1/index.php?title=Jun_Fuku... ) he seems to have a credible background.

Although I find it interesting that he works for Toyota:

> My name is Jun Fukuyama. I’m currently a researcher at Toyota InfoTechnology Center. I’m visiting WINLAB and Civil Engineering department at Rutgers University, working on algorithms and mathematical analysis related to vehicular communications and mobility modeling.

Unless he's been doing this research in his spare time, it seems like an odd fit for Toyota to dedicate research to. Obviously large companies employ theory-oriented researchers, but when I think Toyota I don't really think about very abstract computer science. I'm curious if there are any particular applications for the company one way or the other.

Re: Jun Fukuyama's P≠NP Page

#14

Post by emillon »

SenorWilson wrote: post #7
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.

I think that you mean a NP-complete problem. There's no such thing as a "p-np problem".

Re: Jun Fukuyama's P≠NP Page

#15

Post by tomjakubowski »

B-Con wrote: post #13

From other people's research ( http://michaelnielsen.org/polymath1/index.php?title=Jun_Fuku... ) he seems to have a credible background. Although I find it interesting that he works for Toyota: > My name is Jun Fukuyama. I’m currently a researcher at Toyota InfoTechnology Center. I’m visiting WINLAB and Civil Engineering department at Rutgers University, working on algorithms and mathematical analysis related to vehi…

Toyota actually has opened a school in Chicago specifically for computer science, in conjunction with the University of Chicago:

http://en.wikipedia.org/wiki/Toyota_Technological_Institute_...

Re: Jun Fukuyama's P≠NP Page

#16

Post by dbaupp »

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?

This is a specific case that (maybe) proves the general claim that P != NP.

Proving an inequality is "easy", because only requires a single counterexample: if there is one problem in NP that is not in P (I.e. an NP problem not solvable in polynomial time), then NP can't possible equal P.

Fukuyama is proposing that CLIQUE is such a counter-example.

(Proving the inequality doesn't actually require the special property of NP-completeness which others are talking about; that is only useable in a proof P = NP.)

Re: Jun Fukuyama's P≠NP Page

#18

Post by gburt »

I wish I had the mathematical background to comprehend this. It's very involved. My understanding is that he has shown that CLIQUE (a known NP-complete problem) takes exponential time and thus is not solvable in polytime, this would mean there is a problem outside of P but inside of NP, and this P != NP.

Re: Jun Fukuyama's P≠NP Page

#19

Post by Tloewald »

akavi wrote: post #8
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?

Read it and google as you go. Math is one of the best covered topics online. For a potential millenium prize proof, it seems very approachable. That said, that's not saying much.
Post reply on HN