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

21–30 of 85 posts

Re: Jun Fukuyama's P≠NP Page

#21

Post by ColinWright »

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, deciding if this can be done can be really hard. However, checking if someone has successfully done it is easy.

Motivation for a definition of NP:

A problem for which it is efficient (for which read "polynomial") to check a purported solution is said to be in "NP". Knowing whether a Hamilton cycle exists in a network is one of many, many such problems.

Definition: A problem is in "NP" if there is a polynomial time algorithm to test an alleged solution.

Definition: A problem is in "P" if there is a polynomial time algorithm to solve it.

Lemma: All problems in "P" are also in "NP". Proof left to the interested reader.

(Note: technically we are dealing with Decision Problems - problems where the answer is always Yes or No. For example, I didn't ask you to find a Hamilton Cycle, I only asked if there was one. Sometimes the Decision version can be ramped up into actually finding the solution.)

Note that easy problems (for example, finding a cycle that visits every edge exactly once - an Euler Cycle) is also "NP", but it's not a hard NP problem - it's actually in "P". This point confuses a lot of people. NP does not automatically mean hard - that comes in a minute.

Another example:

Similarly, factoring a large integer can be really hard, but if someone claims to have a factor, checking it is as easy as doing the division.

Comparing problems:

Cleverly, it can be shown that if you can solve the Hamilton Circuit problem efficiently, that can be converted into a way of solving the factoring problem. In some very real sense, the Hamilton Circuit problem is harder than (or equal to) the factoring problem.

Finding:

There are many, many NP problems that have been shown all to be equivalent to each other, all to be easy to check solutions, and yet no algorithm for solving in polynomial time known. Such problems are call NP-Complete (NPC) because an efficient algorithm for any of them will completely solve all the NP problems.

So:

* A problem is said to be in "P" if there is an algorithm that takes instances and produces answers in polynomial time.

* A problem is said to be in "NP" if there is an algorithm that takes only polynomial time to check a purported solution for correctness.

* It is unknown if there are any problems that are in "NP", but not in "P".

That is the P vs NP question, and the Clay Mathematics Institute has offered $10^6 for its resolution. You could do this by showing that there is a polynomial time algorithm for any of the NPC problems, or by showing that no such algorithm exists.

Summary:

* P problems are "easy"

* NPC problems are thought to be hard

* There are lots of NPC problems, and solving any one of them would solve all NP problems.

* Integer factoring (IF) is thought to be outside P, but not as hard as NPC.

* There are problems that are harder than all NPC problems, these are called NP-Hard.

So we think that

  P
But we don't know if these are, in fact, all different. The submitted link is to a paper that says yes, they are all different.

I hope that helps.

Re: Jun Fukuyama's P≠NP Page

#22

Post by bowyakka »

Tloewald wrote: post #19
akavi wrote: post #8

Earlier quoted context omitted.

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.

I am not sure I would consider it approachable, I am lost by page 3

Re: Jun Fukuyama's P≠NP Page

#23

Post by ColinWright »

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…

OK, a little extra, and speaking very informally ...

I've skimmed the first couple of pages, and in essence he seems to be setting up to show that a circuit that's sufficiently complex to solve the clique problem will have to have an exponential number of components. That would imply that any algorithm to solve "Clique" would be exponential, hence super-polynomial, hence not in "P".

Problem is, others have proven that there are technical barriers to this approach, and I see no hint of the author explicitly saying why his approach avoids these problems.

For more about this concern, see points 1, 4, and 6 in this very accessible post:

http://www.scottaaronson.com/blog/?p=458

The PowerPoint talk "Has There Been Progress on the P vs. NP Question?" lunk to at the end of that post (before the comments) is a very good, accessible overview and is an excellent starting point to highlight what you need to follow up on.

Wikipedia's section on why the proof of P=NP or P!=NP is likely to be hard is also useful reading:

http://en.wikipedia.org/wiki/P_versus_NP_problem#Results_abo...

Re: Jun Fukuyama's P≠NP Page

#24

Post by chimeracoder »

dbaupp wrote: post #16
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…

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

Re: Jun Fukuyama's P≠NP Page

#25

Post by ibejoeb »

adamnemecek wrote: post #11
akavi wrote: post #8

Earlier quoted context omitted.

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

Sipser is great. Highly recommended. Working that book really accelerated my understanding. You can go from practically nothing to something with it, though it helps to have some discrete math.

Re: Jun Fukuyama's P≠NP Page

#26

Post by vznvzn »

hi all. meant to post a comment but didnt understand this hackernews interface so far, am brand new to this site. fukuyama states on his web page he's worked on P vs NP for over 10 yrs, both inside and outside of his professional jobs which include research and teaching. the web page is a proof [claimed/attempt] that P!=NP posted on Jul 1. unfortunately its gotten very little to no online attention since then, at this point so far. he doesnt seem to have announced it anywhere in cyberspace, only created the blog.

Re: Jun Fukuyama's P≠NP Page

#27

Post by Aardwolf »

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 one to find the answer.

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?

Re: Jun Fukuyama's P≠NP Page

#28

Post by evincarofautumn »

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?

As a compiler guy, I found that reading a lot of type theory papers helped me really get into the CS theoretical mindset, which made reading mathematics papers a lot easier. Writing a lot of Haskell code didn’t hurt. Oleg Kiselyov has some fairly approachable papers, as do Simon Peyton-Jones and Daan Leijen. Try searching for things on Lambda the Ultimate[1] if you’re interested.

[1]: http://lambda-the-ultimate.org/

Re: Jun Fukuyama's P≠NP Page

#29

Post by [deleted] »

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…

[deleted]

Re: Jun Fukuyama's P≠NP Page

#30

Post by btilly »

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 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 one to find the answer.

It doesn't work that way. The common characteristic of NP-complete problems is that there are an exponential number of possible solutions, but verifying that a purported solution is a solution takes only polynomial time.

For example consider SAT (see http://en.wikipedia.org/wiki/Boolean_satisfiability_problem for more). This is the problem of deciding whether there is a set of possible variable values that make a given Boolean equation evaluate to True. For an equation of length n there are in general O(n) variables, and therefore 2^O(n) possible sets of true/false values that the variables can have. So a brute force search takes exponential time.

But if you give me an equation, AND a set of values for the variables that you claim will result in the final expression evaluating to True, I can verify it in time O(n).

Does that answer your question?

Post reply on HN