Hacker News new | past | comments | ask | show | jobs | submit login

Thanks Mark,

Good work Indeed.

Can you please explain why you think P=NP. I am deeply interested in knowing about them.




to be honest, mostly it's because i enjoy disagreeing with people who are convinced of things they don't have a full understanding of. if you are decently educated, you realize how much there is we don't know, and approach every unsolved puzzle with a combination of curiosity, confidence and humility. philosophy aside, here's my thinking:

LONG VERSION: Suppose P is an NP complete decision problem; for each instance, the answer is either 'yes' or 'no'. Let P have verifying function V. Let the language L be the set of all binary strings s that represent instances of P for which V(s) = 1, i.e. the set of all strings s that represent instances of P for which the answer is 'yes'. If L (the set of all instances of P for which the answer is 'yes') is finite, then you can easily answer all instances of the problem P in constant time by using a lookup table that stores all members of L (i.e. all finite languages are regular.)

So, consider the case when L is infinite. We know that V must be expressible in terms of a finite sequence of symbols. Suppose we have manged to express V using a total of C bits. The entropy of all C-bit binary sequences is bounded by a function of C alone; i.e. it is independent of the specific content of V, all that matters is how many bits are in some (it doesn't matter which) implementation of V. My primitive understanding of information theory tells me that if V has a finite amount of information, and L is uniquely determined by V, then L cannot possibly have MORE information than V; if you have V and enough time, you can compute all of L. This limits the possibilities of L, and suggest to me that there must be a way to find a (possibly complex and incomprehensible algorithm) for solving all instances of P, by 'compressing' L in just the right way. I admit that this is very hand-wavey; i just don't know enough information theory to pin everything down.

SHORT VERSION: if you can verify all solutions to a problem using a function expressible using a finite sequence of symbols, then the total information content of a sequence representing all solutions to the problem can't exceed the information content of the verifying algorithm.

if P != NP, this (to me) implies that a list of answers to a problem somehow has more information than an algorithm that can be used to generate that list of all answers. it seems to me that the algorithm could easily contain more information than the list, but not the other way around.

to put it another way, if you see a verifying function as a compression algorithm on the list of all solutions (because they contain the same amount of information), then P != NP implies that some infinite sequences (which represent np complete problems) are simultaneously so redundant that they can be compressed to a finite length, but at the same time are so complicated that you can't figure out an arbitrary element without doing a massive amount of computation. as i see it, some patterns can appear random unless you look at them from just the right perspective, and then the pattern emerges. because np-complete problems can be expressed with a finite amount of information, there has to be a pattern that we're not seeing yet.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: