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

71–80 of 85 posts

Re: Jun Fukuyama's P≠NP Page

#71

Post by jjjjjosh »

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…

Just to add: NP actually stands for "non-deterministic polynomial," meaning that if we had non-deterministic computers (like the NFAs you may remember from Automata Theory that can explore several different possibilities simultaneously) those types of computers could solve problems in NP in polynomial time.

Re: Jun Fukuyama's P≠NP Page

#72

Post by mdxn »

vznvzn wrote: post #26

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

If you don't mind me asking, how and when did you find his blog post?

Re: Jun Fukuyama's P≠NP Page

#73

Post by kiskis »

bowyakka wrote: post #37
kiskis wrote: post #20

damn, there is a typo on page 32 (in paper version 1.11). Stopped reading. I'm wondering if that voids the proof. Let's the downvote begin.

This is why we cant have nice things

now the funny thing is that there is really a typo on that page, so all of the these hacker news people downvote just because I pointed out some small, but truth parth of reality.

this is called witch-hunt

Re: Jun Fukuyama's P≠NP Page

#74

Post by yuvadam »

jjjjjosh wrote: post #71
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…

Just to add: NP actually stands for "non-deterministic polynomial," meaning that if we had non-deterministic computers (like the NFAs you may remember from Automata Theory that can explore several different possibilities simultaneously) those types of computers could solve problems in NP in polynomial time.

Non-deterministic Turing Machines, specifically. NFAs are obviously much weaker.

Re: Jun Fukuyama's P≠NP Page

#75

Post by drostie »

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…

Just to give a little more context, because I think this gripe is very common:

There exists a proof that NAND gates are all you ever need to compute an arbitrary boolean function from M bits to N bits. Actually, you also need a "copy" gate -- the ability to generate two bits with value X from one bit with value X -- and "wires" to communicate values from gate to gate, but that's about it.

The proof starts out like this: "a function from M bits to N bits is actually just N functions from M bits to 1 bit, as long as I can copy the input N times and feed it to the N functions which compute each output bit. So if I solve the problem for M-to-1, I automatically solve M-to-N as long as I have COPY and SWAP gates."

It's very important to see that the exact same approach is being used in the P-vs-NP question. P and NP are designed to be about functions which take M bits to 1 bit, hence they are "decision problems" with a boolean output but a variable input.

The question "P = NP?" can also be phrased more common-sensically, if not totally precisely, as "is brute force ever really necessary?". What is brute force? It is if you have to try a substantial fraction of the 2^M inputs to find a certain 1-bit output. What does this look like here? Well, that gets more complicated because we use scaling of a problem and a system of solution to discuss what's going on.

So a problem is in NP if (1) you can reduce it to some sort of M-bit input to 1-bit output, and (2) there exists some constant number K such that if I double the input size from M to 2M, the circuit has no more than K times the number of gates. This gives the logic circuit a "polynomial-time" size.

Then a problem is in P if we can find an input which makes the output 1 in a polynomial number of gates as well. Thus this is the "inverse" problem, "find me an input which makes this function 1." In fact we've just defined what's called a "satisfiability problem" -- find an input which satisfies this polynomial-size M-variable boolean formula.

A problem is in NP-complete if the recursion holds: if you can implement COPY and NAND and wires in that system in a polynomial number of gates, so that any problem in NP can be written in terms of your problem. This is part of the value of having these "constant K" constraints rather than specifying a given K; we get to define these NP-complete cases as the "hardest cases in NP," because if you can reverse them, then you can reverse any other problem in NP.

Does that help?

Re: Jun Fukuyama's P≠NP Page

#76

Post by sold »

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

No. P/poly is uncountable (contains every unary language) and NP, NEXP, R etc. are countable.

Re: Jun Fukuyama's P≠NP Page

#77

Post by iso-8859-1 »

albertzeyer wrote: post #49

Btw., what about Vinay Deolalikar's proof now? The last update I could find: http://rjlipton.wordpress.com/2011/08/11/deolalikars-claim-o... http://news.ycombinator.com/item?id=2891710

It is incorrect. I guess that after he realized it himself, he got discouraged and didn't bother to tell people about it.

Re: Jun Fukuyama's P≠NP Page

#78

Post by Mouq »

kiskis wrote: post #73
bowyakka wrote: post #37

Earlier quoted context omitted.

This is why we cant have nice things

now the funny thing is that there is really a typo on that page, so all of the these hacker news people downvote just because I pointed out some small, but truth parth of reality. this is called witch-hunt

Well, sure. It's more that you posted a comment not that there's a typo but that this typo makes it so unbearable to read that you were simply forced to stop. But anyway...

Re: Jun Fukuyama's P≠NP Page

#79

Post by tsahyt »

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.

I'm certainly missing some background but if I had the time I'd work my way through it just for the hell of it. The problem he attempts solving here is extremely important so I welcome any attempts made at it.

Re: Jun Fukuyama's P≠NP Page

#80

Post by kiskis »

Mouq wrote: post #78
kiskis wrote: post #73

Earlier quoted context omitted.

now the funny thing is that there is really a typo on that page, so all of the these hacker news people downvote just because I pointed out some small, but truth parth of reality. this is called witch-hunt

Well, sure. It's more that you posted a comment not that there's a typo but that this typo makes it so unbearable to read that you were simply forced to stop. But anyway...

it will be oil on fire, and you guys will already downvoted me into oblivion, but the truth is the same, the paper has several typos, which makes in unquestionable that it did not see a spell-checker.
Post reply on HN