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

31–40 of 85 posts

Re: Jun Fukuyama's P≠NP Page

#31

Post by habitue »

Aardwolf wrote: post #27
ColinWright wrote: post #21

Very briefly: Context: Some problems are easy, and known to be easy. Some problems appear to be hard, and yet easy to verify alleged solutions. That seems odd - let's have a closer look. Example: Consider being given a network and asked if there's a path that visits every node exactly once and returns to its starting point. (This is the task of asking if a Hamilton Cycle exists). If the network is big enough, decidin…

Why do they call it decision problems, if it's really about finding a solution that is much more than a boolean (like a path, ...)? The whole idea of "verify" versus "find" makes no sense for problems with a yes/no answer, because if you can verify a boolean answer in polynomial time, you can always find the solution in polynomial time too, after all there are only two possible solutions so you need to verify only on…

The decision problem is formulated something like "Is there a hamiltonian path of at most length n" for different n. You can get the actual answer by polling the algorithm that answers the decision problem using a binary search plugging in different values for n (since there is a maximum number of possible paths through a graph with a certain number of nodes)

Re: Jun Fukuyama's P≠NP Page

#33

Post by GoGoGalois »

gburt wrote: post #18

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.

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.

Re: Jun Fukuyama's P≠NP Page

#34

Post by tbmbob »

Aardwolf wrote: post #27
ColinWright wrote: post #21

Very briefly: Context: Some problems are easy, and known to be easy. Some problems appear to be hard, and yet easy to verify alleged solutions. That seems odd - let's have a closer look. Example: Consider being given a network and asked if there's a path that visits every node exactly once and returns to its starting point. (This is the task of asking if a Hamilton Cycle exists). If the network is big enough, decidin…

Why do they call it decision problems, if it's really about finding a solution that is much more than a boolean (like a path, ...)? The whole idea of "verify" versus "find" makes no sense for problems with a yes/no answer, because if you can verify a boolean answer in polynomial time, you can always find the solution in polynomial time too, after all there are only two possible solutions so you need to verify only on…

"If you need extra data to prove this "yes" in polynomial time, then the answer isn't a boolean anymore, but a boolean plus the extra data, so how can you still call that a yes/no problem?"

You are combining two distinct concepts: the answer and the 'evidence'. The answer to an NP-complete problem is always Yes or No. But, we say that we can "verify" a decision problem in polynomial time if, given an answer AND evidence, we can check that the answer is true.

For concreteness: the k-clique problem (determining if there's a clique of at least size k in a graph) is hard. But, if somebody told us the answer was Yes, and gave us appropriate evidence (say, a set of k nodes in the graph which form a clique), verifying would be easy.

Re: Jun Fukuyama's P≠NP Page

#35

Post by morsch »

GoGoGalois wrote: post #33
gburt wrote: post #18

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.

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.

Re: Jun Fukuyama's P≠NP Page

#36

Post by GoGoGalois »

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.

Oh ok, I thought the first post was referring to a single algorithm, not every possible algorithm. My mistake.

Re: Jun Fukuyama's P≠NP Page

#38

Post by jamesjporter »

tomjakubowski wrote: post #15
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_...

I go to UChicago; that place is sort of like an eerie mystery box that nobody ever goes to or talks about. I didn't even find out about it's existence until my 3rd year here. My one friend who's been in there described the experience as really bizarre; it left him half convinced that its actually a front for some sort of Israeli money laundering operation.

Re: Jun Fukuyama's P≠NP Page

#39

Post by PeterBB »

chimeracoder wrote: post #24
dbaupp wrote: post #16

Earlier quoted context omitted.

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…

> Proving an inequality is "easy", because only requires a single counterexample: Proving an equality isn't exactly "harder" (no NP-hard pun intended) - all you have to do is show that a single NP-complete problem can be reduced to a problem within P in polynomial time.

That's true in this case, but only because we have other results showing that various problems are NP-complete.

Re: Jun Fukuyama's P≠NP Page

#40

Post by sjg007 »

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

This only works if all NPC problems can be converted to CLIQUE?
Post reply on HN